Pascal's triangle and the binomial theorem

Combinations have a remarkable structure that lets them be computed without ever touching factorials: Pascal's triangle.

Pascal's rule

C(n,k) = C(n-1, k-1) + C(n-1, k)

The proof fits in one sentence. To form a committee of k people among n, look at one particular person — say Alice:

either Alice is IN the committee -> k-1 seats left among n-1 -> C(n-1,k-1)
or she is NOT                    -> k   seats left among n-1 -> C(n-1,k)

The two cases are exclusive and cover everything: add them.

The triangle

Each number is the sum of the two above it:

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
                     \ | /
                      \|/          15 + 6 = 21  ->  next row

It gives C(6,2) = 15, C(5,3) = 10 directly, with no factorial computation at all.

Two useful properties

SYMMETRY:   C(n,k) = C(n, n-k)

Choosing 3 people among 10 is also choosing the 7 you leave out. In practice always compute from the smaller side: C(50,48) is computed as C(50,2) = 1225, in two multiplications instead of forty-eight.

ROW SUM:   C(n,0) + C(n,1) + ... + C(n,n) = 2^n

Counting all subsets of an n-element set, group by group size, amounts to counting them all at once: each element is either in or out, giving 2^n subsets.

The binomial theorem

The same numbers appear in the expansion of powers:

(a + b)^n = C(n,0)a^n + C(n,1)a^(n-1)b + ... + C(n,n)b^n

(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴
              ^     ^      ^      ^    ^
              1     4      6      4    1     <- row n = 4 of the triangle

Why? Expanding (a+b)(a+b)(a+b)(a+b), each term is built by choosing a or b in each bracket. The coefficient of a²b² counts the number of ways of choosing in which 2 brackets out of 4 to take the b: exactly C(4,2) = 6.

The link with probability

This reading — "in how many brackets did I take b?" — is exactly the reasoning behind the binomial distribution. Repeating an experiment with two outcomes n times and counting successes produces C(n,k) in the same way. Pascal's triangle is therefore the skeleton of the next course.

Summary

• Pascal's rule: C(n,k) = C(n-1,k-1) + C(n-1,k), hence the triangle.
• Symmetry: C(n,k) = C(n,n-k) — always compute from the smaller side.
• Row sum: 2^n, the total number of subsets of a set.
• Binomial theorem: the C(n,k) are the coefficients of (a+b)^n.
• The coefficient counts in which brackets b was chosen — the very reasoning of the binomial distribution.