Combinations & Pascal's Triangle

May 2026 · 22 min read

Permutations count arrangements: order matters. Combinations count selections: order does not. The shift from one to the other is small in symbols and huge in consequence — it gives us $\binom{n}{r}$, the binomial coefficient, a number that quietly powers most of probability theory.

From Permutations to Combinations

How many ways can we choose 3 students from a class of 5 to form a committee? If we cared about which student is the chair, secretary, and treasurer (an ordered choice), we would compute

$P(5, 3) = \dfrac{5!}{2!} = 60.$

But we just want a committee — the same three students no matter which order we list them. Each unordered committee of 3 corresponds to exactly $3!$ ordered arrangements (any of the 3 could be listed first, any of the remaining 2 second, the last one third). So we have to divide by the over-count:

$\binom{5}{3} = \dfrac{P(5,3)}{3!} = \dfrac{60}{6} = 10.$

Whenever you see a problem asking "how many ways to pick a group" without caring about order, you're looking at $\binom{n}{r}$.

Basic Properties

1. Boundary values. $\binom{n}{0} = \binom{n}{n} = 1$ — there is exactly one empty subset and exactly one full subset.
2. Symmetry. $\binom{n}{r} = \binom{n}{n - r}$. Choosing the $r$ to include is the same as choosing the $n-r$ to leave out.
3. Sum across a row. $\sum_{r=0}^{n} \binom{n}{r} = 2^n$. This is the count of all subsets, big and small. Each element either is or isn't in the subset, giving $2^n$ total.
4. Alternating sum. $\sum_{r=0}^{n} (-1)^r \binom{n}{r} = 0$ for $n \ge 1$. There are exactly as many even-sized as odd-sized subsets.

Pascal's Identity

This identity is the most useful relation in elementary combinatorics. Algebraically you can verify it by writing both sides over a common denominator, but the combinatorial proof is more illuminating.

Combinatorial proof.

Suppose we want to choose an $r$-element subset from $\{1, 2, \dots, n\}$. Look at element $n$. Every $r$-subset either contains element $n$ or it doesn't:

• Contains $n$. Then we must still choose $r - 1$ items from the remaining $\{1, \dots, n-1\}$. That is $\binom{n-1}{r-1}$ ways.
• Does not contain $n$. Then we choose all $r$ items from $\{1, \dots, n-1\}$. That is $\binom{n-1}{r}$ ways.

The two cases are disjoint and cover all $r$-subsets, so by the addition rule from Part 2:

$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}.\quad\Box$

This kind of "split by inclusion or exclusion of a single element" argument is your bread and butter in combinatorial proofs.

Pascal's Triangle

Arrange the binomial coefficients in a triangle whose $n$-th row contains $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$:

n=0:                          1
n=1:                       1     1
n=2:                    1     2     1
n=3:                 1     3     3     1
n=4:              1     4     6     4     1
n=5:           1     5    10    10     5     1
n=6:        1     6    15    20    15     6     1

Pascal's identity says: each entry is the sum of the two entries diagonally above it. The 1s on the boundary come from $\binom{n}{0} = \binom{n}{n} = 1$. Everything else fills in by addition.

Hockey Stick Identity

Drawn on Pascal's triangle, the left side is a diagonal "stick" that bends at the bottom — hence the name.

Combinatorial proof. The right side counts $(r+1)$-subsets of $\{1, 2, \dots, n+1\}$. Group these subsets by their largest element $k$. For each $k \in \{r+1, r+2, \dots, n+1\}$, the remaining $r$ elements come from $\{1, \dots, k-1\}$, giving $\binom{k-1}{r}$ choices. Summing over $k$ and reindexing $i = k - 1$ gives the left-hand side. $\Box$

Vandermonde's Identity

Combinatorial proof. Imagine a class of $m$ boys and $n$ girls, and we want to pick a committee of $r$ students. The right side conditions on $k$, the number of boys: choose $k$ boys from $m$ and $r-k$ girls from $n$, then sum over all valid $k$. The left side is the same count without conditioning. $\Box$

Setting $m = n = r$ gives the elegant special case

$\displaystyle \binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^2,$

using the symmetry $\binom{n}{r} = \binom{n}{n-r}$ on the second factor.

Why $\binom{n}{r}$ Appears Everywhere

$\binom{n}{r}$ counts a remarkable number of seemingly unrelated structures:

• $r$-subsets of an $n$-set.
• Lattice paths from $(0,0)$ to $(r, n-r)$ using only east and north steps. Each path is a sequence of $n$ moves containing exactly $r$ easts.
• Binary strings of length $n$ with exactly $r$ ones.
• Pull-down sequences: ways to flip a coin $n$ times and see exactly $r$ heads (we will use this constantly in probability).
• Polynomial expansions: the coefficient of $x^r y^{n-r}$ in $(x + y)^n$. Part 5 makes this precise.

Worked Examples from Ross

Ross 1.4a — Committee selection

How many committees of 3 can be formed from 20 people?

$\displaystyle \binom{20}{3} = \dfrac{20 \cdot 19 \cdot 18}{3!} = \dfrac{6840}{6} = 1140.$

Ross 1.4b — Committee with constraints

From 5 women and 7 men, how many committees of 2 women and 3 men are possible?

Multiply the choices in each gender independently:

$\binom{5}{2} \cdot \binom{7}{3} = 10 \cdot 35 = 350.$

Ross 1.4b (variant) — Committee with a feud

Same as above, but two of the men refuse to serve together.

Use complement counting: total committees minus committees containing both feuding men. The "both feuders" case fixes 2 of the 3 men, so we need 1 more man from the remaining 5, and 2 women from 5:

$\binom{5}{2}\binom{7}{3} - \binom{5}{2}\binom{5}{1} = 350 - 50 = 300.$

Worked: poker hands

How many 5-card hands can be dealt from a standard 52-card deck?

Order does not matter — we hold a hand, not a sequence. So $\binom{52}{5} = 2{,}598{,}960$.

How many of those are flushes (5 cards of the same suit)?

Pick the suit (4 ways), then 5 cards from that 13-card suit: $4 \cdot \binom{13}{5} = 4 \cdot 1287 = 5148$. (Some authors subtract straight flushes; that is a refinement, not a different counting principle.)

When to Divide vs. When to Subtract

Two complementary counting moves keep showing up:

Computing Binomial Coefficients

For a single $\binom{n}{r}$ with small $r$, compute directly:

// O(r) integer math, careful with overflow.
long long C(int n, int r) {
    if (r < 0 || r > n) return 0;
    if (r > n - r) r = n - r;
    long long result = 1;
    for (int i = 0; i < r; i++) {
        result *= (n - i);
        result /= (i + 1);
    }
    return result;
}

For many queries modulo a prime $p$, precompute factorials and inverse factorials (see Part 3):

long long C(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD;
}

For very large $n$ with small $r$, use the falling-factorial form $\binom{n}{r} = \prod_{i=0}^{r-1} \dfrac{n-i}{i+1}$ to keep numbers from blowing up.

Common Mistakes

• Forgetting symmetry. $\binom{100}{98}$ is just $\binom{100}{2} = 4950$ — much easier.
• Confusing "at least 2" and "exactly 2". "At least 2" sums multiple $\binom{}{}$ terms or uses complement counting.
• Multiplying when you should divide. If a problem says "choose any 3 from these 10 then arrange them", that is $\binom{10}{3} \cdot 3! = P(10, 3)$ — but if it says "choose 3 to be on a committee", arrangement is irrelevant.
• Leaving repetitions unchecked. If selections can repeat, you need stars-and-bars (Part 7), not $\binom{n}{r}$.

Summary

• $\binom{n}{r} = \dfrac{n!}{r!(n-r)!}$ counts unordered $r$-subsets of an $n$-set.
• $\binom{n}{r} = \binom{n}{n-r}$ (symmetry) and $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ (Pascal's identity).
• Pascal's triangle is just Pascal's identity unrolled.
• Hockey-stick and Vandermonde are powerful sum identities; both have crisp combinatorial proofs.

Practice Problems

• Ross 1.18. A committee of 7 is to be selected from a group of 10 women and 9 men. If 3 men and 4 women are required, how many possible committees are there?
• Ross 1.20. A person has 8 friends, of whom 5 will be invited to a party. How many choices are there if 2 of the friends are feuding and will not attend together?
• Ross 1.21. Consider the grid of points shown in Figure 1.4. Suppose that, starting at the point labelled $A$, you can go one step up or one step to the right at each move. This procedure is continued until $B$ is reached. How many different paths from $A$ to $B$ are possible? lattice paths
• Practice — bridge. How many bridge hands (13 cards from 52) contain exactly 4 spades, 3 hearts, 4 diamonds, and 2 clubs?
• Practice — sum of binomials. Prove that $\sum_{k=0}^{n} k \binom{n}{k} = n 2^{n-1}$. combinatorial double-counting; pick a committee with a chair
• LeetCode 62 — Unique Paths. Number of paths in an $m \times n$ grid — this is exactly $\binom{m+n-2}{m-1}$.
• LeetCode 119 — Pascal's Triangle II. Generate row $n$ of Pascal's triangle in $O(n)$ space.