The many faces of the binomial coefficient: why nCr is so ubiquitous

Through Pascal's triangle, lattice paths, and the binomial theorem, we uncover the many identities of the binomial coefficient. We also cover the computational machinery essential for competitive programming: factorial tables with modular inverses, and Lucas' theorem for enormous indices.

Folio Official

March 1, 2026

The binomial coefficient $(r n)$ begins life with the modest meaning "the number of ways to choose $r$ objects from $n$ ." Yet it appears everywhere in mathematics: in Pascal's triangle, in lattice path enumeration, in the expansion of $(x + y)^{n}$ , and in modular arithmetic for competitive programming. Why is $(r n)$ so ubiquitous?

1 Definition and basic properties

Definition 1 (Binomial coefficient).

For non-negative integers

n

and

r

with

0 \leq r \leq n

, the binomial coefficient is

(r n) = \frac{n !}{r ! ( n - r )!} .

When

r > n

, we set

(r n) = 0

Remark 2.

That

(r n)

is always an integer is not obvious from the formula: a quotient of factorials need not be an integer in general. But from the combinatorial interpretation – the number of ways to choose

r

objects from

n

– it must be a non-negative integer. This tension between algebraic non-obviousness and combinatorial transparency is one of the charming features of the binomial coefficient.

2 Pascal's identity: the recursive structure

Theorem 3 (Pascal's identity).

For

1 \leq r \leq n - 1

(r n) = (r - 1 n - 1) + (r n - 1) .

Proof.

Fix a particular element

x

among the

n

objects. Every

r

-element subset either contains

x

or does not.

If it contains

x

, we must choose the remaining

r - 1

elements from the other

n - 1

objects, giving

(r - 1 n - 1)

subsets.

If it does not contain

x

, all

r

elements come from the remaining

n - 1

objects, giving

(r n - 1)

subsets.

These two cases are mutually exclusive, so by the addition principle,

(r n) = (r - 1 n - 1) + (r n - 1)

. □

Remark 4.

Pascal's identity generates Pascal's triangle: each row lists

(0 n), (1 n), \dots, (n n)

, and every entry is the sum of the two entries directly above it. From a computational point of view, Pascal's triangle is nothing other than a DP table – a dynamic programming table whose recurrence is Pascal's identity, filled row by row.

3 Lattice paths

Theorem 5 (Lattice path count).

The number of shortest lattice paths from

(0, 0)

(a, b)

– where each step moves one unit right or one unit up – is

(a a + b)

Proof.

A shortest path consists of exactly

a

rightward steps and

b

upward steps, in some order. The path is determined by choosing which

a

of the

a + b

total steps are rightward, so the count is

(a a + b)

. □

Example 6.

The number of shortest lattice paths from

(0, 0)

(3, 2)

(3 5) = 10

. Two such paths are RRUРУ and URRRУ (where R denotes right and U denotes up).

Remark 7.

The lattice path interpretation is remarkably powerful. Pascal's identity, in this language, says that any path reaching

(a, b)

arrives either from

(a - 1, b)

(having taken a rightward step) or from

(a, b - 1)

(having taken an upward step). The recurrence is nothing but the observation that every path has a last step.

4 The binomial theorem

Theorem 8 (Binomial theorem).

For any

x, y

and non-negative integer

n

(x + y)^{n} = r = 0 \sum n (r n) x^{r} y^{n - r} .

Proof.

Expand

(x + y)^{n} = (x + y) (x + y) \dots (x + y)

by choosing either

x

y

from each of the

n

factors and multiplying the choices together. The term

x^{r} y^{n - r}

arises precisely when

x

is chosen from

r

of the

n

factors, and the number of ways to make that selection is

(r n)

. □

Example 9 (Special values).

Setting

x = y = 1

yields

\sum_{r = 0}^{n} (r n) = 2^{n}

, which is the total number of subsets of an

n

-element set. Setting

x = 1, y = - 1

yields

\sum_{r = 0}^{n} (- 1)^{r} (r n) = 0

, revealing that the number of even-sized subsets equals the number of odd-sized subsets.

5 Fast computation modulo a prime

In competitive programming, one frequently needs $(r n) mod p$ where $p$ is a prime (typically $p = 1 0^{9} + 7$ ).

Remark 10 (Factorial table with modular inverses).

The following preprocessing, done in

O (n)

time, enables

O (1)

queries:

Build a factorial table: $fact [i] = i! mod p$ for $i = 0, 1, \dots, n$ .
Build an inverse factorial table: $inv_fact [i] = (i!)^{- 1} mod p$ , using Fermat's little theorem ( $a^{p - 1} \equiv 1 (mod p)$ implies $a^{- 1} \equiv a^{p - 2} (mod p)$ ).

Then

(r n) \equiv fact [n] \cdot inv_fact [r] \cdot inv_fact [n - r] (mod p)

, computed in

O (1)

6 Lucas' theorem

Theorem 11 (Lucas' theorem).

Let

p

be a prime. Write

n

and

r

in base

p

n = \sum n_{i} p^{i}

and

r = \sum r_{i} p^{i}

. Then

(r n) \equiv i \prod (r _{i} n _{i}) (mod p) .

Remark 12.

Lucas' theorem is invaluable when

n

is astronomically large (say

n > 1 0^{18}

) but

p

is small. Each digit-level binomial coefficient

(r _{i} n _{i})

involves values less than

p

and can be computed without any precomputation. When

p

is large, however, the factorial-table method is usually more practical.

7 Takeaway

The binomial coefficient wears many hats: subset selection, lattice paths, polynomial expansion, set partition, and more.
Pascal's identity is the source of its recursive structure – and, equivalently, of the DP table known as Pascal's triangle.
The binomial theorem bridges algebra and combinatorics.
For computation modulo a prime, the factorial table with modular inverses handles most cases; Lucas' theorem covers extremely large indices with small primes.

In the next article, we investigate the curious "add, subtract, add, subtract..." pattern of the inclusion–exclusion principle and ask what makes the alternating signs give the right answer.

Combinatorics Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The many faces of the binomial coefficient: why nCr is so ubiquitous

Folio Official

March 1, 2026

1 Definition and basic properties

Definition 1 (Binomial coefficient).

For non-negative integers

n

and

r

with

0 \leq r \leq n

, the binomial coefficient is

(r n) = \frac{n !}{r ! ( n - r )!} .

When

r > n

, we set

(r n) = 0

Remark 2.

That

(r n)

is always an integer is not obvious from the formula: a quotient of factorials need not be an integer in general. But from the combinatorial interpretation – the number of ways to choose

r

objects from

n

– it must be a non-negative integer. This tension between algebraic non-obviousness and combinatorial transparency is one of the charming features of the binomial coefficient.

2 Pascal's identity: the recursive structure

Theorem 3 (Pascal's identity).

For

1 \leq r \leq n - 1

(r n) = (r - 1 n - 1) + (r n - 1) .

Proof.

Fix a particular element

x

among the

n

objects. Every

r

-element subset either contains

x

or does not.

If it contains

x

, we must choose the remaining

r - 1

elements from the other

n - 1

objects, giving

(r - 1 n - 1)

subsets.

If it does not contain

x

, all

r

elements come from the remaining

n - 1

objects, giving

(r n - 1)

subsets.

These two cases are mutually exclusive, so by the addition principle,

(r n) = (r - 1 n - 1) + (r n - 1)

. □

Remark 4.

Pascal's identity generates Pascal's triangle: each row lists

(0 n), (1 n), \dots, (n n)

3 Lattice paths

Theorem 5 (Lattice path count).

The number of shortest lattice paths from

(0, 0)

(a, b)

– where each step moves one unit right or one unit up – is

(a a + b)

Proof.

A shortest path consists of exactly

a

rightward steps and

b

upward steps, in some order. The path is determined by choosing which

a

of the

a + b

total steps are rightward, so the count is

(a a + b)

. □

Example 6.

The number of shortest lattice paths from

(0, 0)

(3, 2)

(3 5) = 10

. Two such paths are RRUРУ and URRRУ (where R denotes right and U denotes up).

Remark 7.

The lattice path interpretation is remarkably powerful. Pascal's identity, in this language, says that any path reaching

(a, b)

arrives either from

(a - 1, b)

(having taken a rightward step) or from

(a, b - 1)

(having taken an upward step). The recurrence is nothing but the observation that every path has a last step.

4 The binomial theorem

Theorem 8 (Binomial theorem).

For any

x, y

and non-negative integer

n

(x + y)^{n} = r = 0 \sum n (r n) x^{r} y^{n - r} .

Proof.

Expand

(x + y)^{n} = (x + y) (x + y) \dots (x + y)

by choosing either

x

y

from each of the

n

factors and multiplying the choices together. The term

x^{r} y^{n - r}

arises precisely when

x

is chosen from

r

of the

n

factors, and the number of ways to make that selection is

(r n)

. □

Example 9 (Special values).

Setting

x = y = 1

yields

\sum_{r = 0}^{n} (r n) = 2^{n}

, which is the total number of subsets of an

n

-element set. Setting

x = 1, y = - 1

yields

\sum_{r = 0}^{n} (- 1)^{r} (r n) = 0

, revealing that the number of even-sized subsets equals the number of odd-sized subsets.

5 Fast computation modulo a prime

In competitive programming, one frequently needs $(r n) mod p$ where $p$ is a prime (typically $p = 1 0^{9} + 7$ ).

Remark 10 (Factorial table with modular inverses).

The following preprocessing, done in

O (n)

time, enables

O (1)

queries:

Build a factorial table: $fact [i] = i! mod p$ for $i = 0, 1, \dots, n$ .
Build an inverse factorial table: $inv_fact [i] = (i!)^{- 1} mod p$ , using Fermat's little theorem ( $a^{p - 1} \equiv 1 (mod p)$ implies $a^{- 1} \equiv a^{p - 2} (mod p)$ ).

Then

(r n) \equiv fact [n] \cdot inv_fact [r] \cdot inv_fact [n - r] (mod p)

, computed in

O (1)

6 Lucas' theorem

Theorem 11 (Lucas' theorem).

Let

p

be a prime. Write

n

and

r

in base

p

n = \sum n_{i} p^{i}

and

r = \sum r_{i} p^{i}

. Then

(r n) \equiv i \prod (r _{i} n _{i}) (mod p) .

Remark 12.

Lucas' theorem is invaluable when

n

is astronomically large (say

n > 1 0^{18}

) but

p

is small. Each digit-level binomial coefficient

(r _{i} n _{i})

involves values less than

p

and can be computed without any precomputation. When

p

is large, however, the factorial-table method is usually more practical.

7 Takeaway

The binomial coefficient wears many hats: subset selection, lattice paths, polynomial expansion, set partition, and more.
Pascal's identity is the source of its recursive structure – and, equivalently, of the DP table known as Pascal's triangle.
The binomial theorem bridges algebra and combinatorics.
For computation modulo a prime, the factorial table with modular inverses handles most cases; Lucas' theorem covers extremely large indices with small primes.

In the next article, we investigate the curious "add, subtract, add, subtract..." pattern of the inclusion–exclusion principle and ask what makes the alternating signs give the right answer.

Combinatorics Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The many faces of the binomial coefficient: why nCr is so ubiquitous

1 Definition and basic properties

2 Pascal's identity: the recursive structure

3 Lattice paths

4 The binomial theorem

5 Fast computation modulo a prime

6 Lucas' theorem

7 Takeaway

Share your expertise with the world

More from Folio Official

Recurrences and generating functions: what happens when you turn a sequence into a function

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

The many faces of the binomial coefficient: why nCr is so ubiquitous

1 Definition and basic properties

2 Pascal's identity: the recursive structure

3 Lattice paths

4 The binomial theorem

5 Fast computation modulo a prime

6 Lucas' theorem

7 Takeaway

Share your expertise with the world

More from Folio Official

Recurrences and generating functions: what happens when you turn a sequence into a function

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem