Binomial coefficients

The numbers $(\binom{n}{k})$ turn up in counts of committees, lattice paths and bit strings, and they satisfy a crowd of identities that look, when proved by pushing factorials around, like accidents of algebra.

They are not accidents. This lesson proves them with a method that runs through the rest of the course: find one set, count it in two different ways, and set the two answers equal. Each identity then says something you can see, rather than something you have to trust. The same idea explains why these numbers appear as the coefficients when $(x + y)^{n}$ is multiplied out, which is where their name comes from. The lesson assumes the previous one, which defined $(\binom{n}{k})$ as the number of $k$ element subsets of an $n$ element set, and it recalls whatever else it needs.

Pascal's rule

Recall the formula. Choosing $k$ things in order from $n$ can be done in $n (n - 1) \dots (n - k + 1)$ ways by the product rule, and each unordered choice has been counted once for each of its $k!$ orders, so

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}

for $0 \leq k \leq n$ . For $k$ outside that range there are no such subsets, and $(\binom{n}{k}) = 0$ , a convention that saves a great many special cases below. So ten people can form $(\binom{10}{3}) = 120$ committees of three.

The formula is symmetric in $k$ and $n - k$ , so $(\binom{n}{k}) = (\binom{n}{n - k})$ . The explanation is a bijection, a function pairing two sets perfectly with nothing left over: send each $k$ element subset to its complement, the $n - k$ elements left behind. Different subsets have different complements, and every $n - k$ element subset is the complement of exactly one $k$ element subset, so the two collections have the same size. Choosing three people for a committee is the same act as choosing seven to stay at home.

The rule that generates everything else is Pascal's rule: for $1 \leq k \leq n$ ,

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

Here is a proof that uses no factorials. Count the $k$ person committees drawn from $n$ people, one of whom is called Ada. Every committee either includes Ada or does not, and those two kinds do not overlap, so by the sum rule their counts add. A committee that includes Ada is fixed by choosing its other $k - 1$ members from the remaining $n - 1$ people, in $(\binom{n - 1}{k - 1})$ ways. A committee that leaves her out takes all $k$ members from the other $n - 1$ , in $(\binom{n - 1}{k})$ ways. The total is $(\binom{n}{k})$ by definition, and the rule is proved.

The algebraic proof, putting both fractions over $k! (n - k)!$ , is correct but gives no reason for the answer to be so simple. The committee proof gives the reason: Ada is either in or out.

Laid out in rows, with row $n$ holding $(\binom{n}{0})$ to $(\binom{n}{n})$ , Pascal's rule says each entry is the sum of the two above it. Rows $0$ to $6$ read $1$ ; $1, 1$ ; $1, 2, 1$ ; $1, 3, 3, 1$ ; $1, 4, 6, 4, 1$ ; $1, 5, 10, 10, 5, 1$ ; and $1, 6, 15, 20, 15, 6, 1$ . Blaise Pascal wrote the triangle up systematically in his Traité du triangle arithmétique of 1654, but it is far older: Yang Hui printed it in 1261, crediting Jia Xian two centuries earlier, and in China it still carries Yang Hui's name.

Counting in two ways

Pascal's rule was proved by a pattern worth naming. Pick a set, here the committees. Count it one way, getting the left side, and another way, getting the right. Both answers count the same set, so they are equal. This is double counting, and its one real difficulty is choosing the set.

A good first test is the identity

k (\binom{n}{k}) = n (\binom{n - 1}{k - 1})

To see it, count the committees of $k$ people from $n$ in which one member is marked as chair. First choose the committee, in $(\binom{n}{k})$ ways, and then its chair from among its $k$ members, giving $k (\binom{n}{k})$ . Alternatively, choose the chair first from all $n$ people, then fill the other $k - 1$ seats from the $n - 1$ left, giving $n (\binom{n - 1}{k - 1})$ . Same set, two counts, and the identity follows.

Example. Check the chair identity with $n = 12$ and $k = 5$ , and say what the common number counts.

The left side is $5 (\binom{12}{5}) = 5 \times 792 = 3960$ . The right side is $12 (\binom{11}{4}) = 12 \times 330 = 3960$ . Both count the ways a club of twelve can form a five person committee with one member as chair: $792$ committees, each with five possible chairs, or twelve possible chairs, each with $330$ ways to fill the remaining four seats.

Now you. Prove that $(\binom{n}{k}) (\binom{k}{m}) = (\binom{n}{m}) (\binom{n - m}{k - m})$ for $0 \leq m \leq k \leq n$ by counting one set in two ways, and check it with $n = 10$ , $k = 4$ , $m = 2$ .

Answer

Count the ways to choose a committee of $k$ from $n$ people together with a subcommittee of $m$ inside it. Choosing the committee first and then the subcommittee from its members gives $(\binom{n}{k}) (\binom{k}{m})$ . Choosing the subcommittee first from everyone, then the other $k - m$ committee members from the $n - m$ people outside it, gives $(\binom{n}{m}) (\binom{n - m}{k - m})$ . With the numbers, $210 \times 6 = 1260$ and $45 \times 28 = 1260$ .

The binomial theorem

Multiply out $(x + y)^{3}$ and the coefficients are $1, 3, 3, 1$ , row $3$ of the triangle. Multiply out $(x + y)^{4}$ and they are $1, 4, 6, 4, 1$ . The pattern is the binomial theorem:

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k}

Write $(x + y)^{n}$ as $n$ brackets multiplied together. Expanding the product means choosing one term, $x$ or $y$ , from each bracket, multiplying the choices, and adding up the results over every possible set of choices, $2^{n}$ of them in all. A set of choices gives $x^{n - k} y^{k}$ exactly when $y$ was taken from $k$ of the brackets and $x$ from the rest. So the coefficient of $x^{n - k} y^{k}$ is the number of ways to choose which $k$ of the $n$ brackets supply the $y$ , and that is $(\binom{n}{k})$ .

This is why the numbers are called binomial coefficients. It also explains Pascal's rule again: in $(x + y)^{n} = (x + y) (x + y)^{n - 1}$ , the first bracket supplies either the $y$ or the $x$ of a term $x^{n - k} y^{k}$ , giving $(\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ . That bracket plays the part of Ada.

Example. Find the coefficient of $x^{2}$ in $(2 x - 3)^{5}$ .

Treat $2 x$ and $- 3$ as the two terms of the binomial. The general term is $(\binom{5}{k}) (2 x)^{5 - k} (- 3)^{k}$ , and it contains $x^{2}$ when $5 - k = 2$ , that is $k = 3$ . The coefficient is $(\binom{5}{3}) \times 2^{2} \times (- 3)^{3} = 10 \times 4 \times (- 27) = - 1080$ . Writing the general term out in full first guards against the two usual slips: leaving the $2$ unpowered and losing the sign.

Now you. Find the coefficient of $x^{5}$ in $(x - 2)^{8}$ .

Answer

The general term is $(\binom{8}{k}) x^{8 - k} (- 2)^{k}$ , and $8 - k = 5$ gives $k = 3$ . The coefficient is $(\binom{8}{3}) \times (- 2)^{3} = 56 \times (- 8) = - 448$ .

The sum of a row

Add up the entries of any row of the triangle: $1 + 4 + 6 + 4 + 1 = 16$ , and $1 + 6 + 15 + 20 + 15 + 6 + 1 = 64$ . The general statement is

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}

and it has two proofs, one from each side of this lesson. The algebraic one sets $x = y = 1$ in the binomial theorem, so the left side is $2^{n}$ and the right is the sum of the row. The counting one needs no theorem at all. An $n$ element set has $2^{n}$ subsets, since each element is independently in or out, and each subset has some size between $0$ and $n$ . Sorting the subsets by size, there are $(\binom{n}{k})$ of size $k$ , and the sizes do not overlap, so the sum rule adds them up to $2^{n}$ . The row sum is the total number of subsets, counted by size.

Setting $x = 1$ and $y = - 1$ instead gives an alternating sum:

(\binom{n}{0}) - (\binom{n}{1}) + (\binom{n}{2}) - \dots + (- 1)^{n} (\binom{n}{n}) = 0

for $n \geq 1$ , since the left side of the theorem is $0^{n}$ . In counting terms, a nonempty set has exactly as many subsets of even size as of odd size, and a bijection shows it directly. Fix one element, say $a$ . Pair each subset with the subset obtained by toggling $a$ : adding it if absent, removing it if present. Toggling changes the size by one, swapping even with odd, and undoes itself, so the pairing is perfect. For $n = 6$ that is $32$ even subsets and $32$ odd ones.

The chair identity combines with the row sum to give one more. Summing $k (\binom{n}{k})$ over all $k$ counts every committee of every size with a chair; choosing the chair first, in $n$ ways, and then any subset of the other $n - 1$ people to join, gives $n \cdot 2^{n - 1}$ . For $n = 5$ both sides are $80$ .

Vandermonde's identity

A department has $m$ mathematicians and $n$ physicists, and needs a committee of $r$ . Counted directly, there are $(\binom{m + n}{r})$ committees. Counted by how many mathematicians sit on it, a committee with exactly $k$ mathematicians is a choice of $k$ from $m$ and $r - k$ from $n$ , in $(\binom{m}{k}) (\binom{n}{r - k})$ ways, and different values of $k$ do not overlap. So

\sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k}) = (\binom{m + n}{r})

which is Vandermonde's identity, named after Alexandre-Théophile Vandermonde, who published it in 1772. Zhu Shijie had stated it in China in 1303. The convention that $(\binom{n}{k}) = 0$ outside $0 \leq k \leq n$ quietly handles the cases where $k$ exceeds $m$ or $r - k$ exceeds $n$ .

The binomial theorem gives a second proof, which is worth seeing because it is the model for a technique of a later lesson. Since $(1 + x)^{m} (1 + x)^{n} = (1 + x)^{m + n}$ , the coefficients of $x^{r}$ on the two sides must agree. On the right it is $(\binom{m + n}{r})$ . On the left, an $x^{r}$ arises by taking $x^{k}$ from the first factor, with coefficient $(\binom{m}{k})$ , and $x^{r - k}$ from the second, with coefficient $(\binom{n}{r - k})$ , summed over $k$ . The two proofs are the same argument: the first factor is the mathematicians.

Example. A panel of four is chosen from five chemists and six biologists. Count the panels by the number of chemists on them, and check the total against Vandermonde.

With $k$ chemists the count is $(\binom{5}{k}) (\binom{6}{4 - k})$ . For $k = 0$ to $4$ that gives $1 \times 15 = 15$ , then $5 \times 20 = 100$ , then $10 \times 15 = 150$ , then $10 \times 6 = 60$ , then $5 \times 1 = 5$ . The sum is $330$ , and $(\binom{11}{4}) = 330$ , the number of ways to pick four from all eleven.

Now you. Use Vandermonde's identity to show that $\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n})$ , and check it for $n = 5$ .

Answer

Take $m = n$ and $r = n$ , so the identity reads $\sum_{k} (\binom{n}{k}) (\binom{n}{n - k}) = (\binom{2 n}{n})$ , and symmetry replaces $(\binom{n}{n - k})$ by $(\binom{n}{k})$ . For $n = 5$ the squares of the row are $1, 25, 100, 100, 25, 1$ , which sum to $252$ , and $(\binom{10}{5}) = 252$ .

The identity has a picture in lattice paths, routes of unit steps right and up: an $n$ by $n$ grid has $(\binom{2 n}{n})$ corner to corner paths, and sorting them by where they cross the diagonal from top left to bottom right gives $n + 1$ groups of sizes ${(\binom{n}{k})}^{2}$ .

The hockey stick

Run down a diagonal of the triangle and add: $1 + 3 + 6 + 10 + 15 = 35$ , and $35$ sits in the next row, just below and to one side of the last entry, so that the numbers summed and the answer trace the shape of a hockey stick. In symbols, for $r \leq n$ ,

\sum_{i = r}^{n} (\binom{i}{r}) = (\binom{n + 1}{r + 1})

and the example is $r = 2$ , $n = 6$ , with $(\binom{7}{3}) = 35$ .

To prove it, count the $(r + 1)$ element subsets of ${1, 2, \dots, n + 1}$ , which number $(\binom{n + 1}{r + 1})$ directly. Sort them instead by their largest element. If the largest element is $i + 1$ , the other $r$ elements are chosen freely from ${1, \dots, i}$ , in $(\binom{i}{r})$ ways, and the largest element can be anything from $r + 1$ up to $n + 1$ . Summing over it gives the left side. A second proof applies Pascal's rule to $(\binom{n + 1}{r + 1})$ , splits off $(\binom{n}{r})$ , applies it again to what remains, and keeps going; the chain unrolls into the diagonal.

With $r = 1$ the identity is the familiar $1 + 2 + \dots + n = (\binom{n + 1}{2}) = \frac{n (n + 1)}{2}$ . With $r = 2$ it adds up the triangular numbers, and it answers a question every December. In the song The Twelve Days of Christmas, the gifts on day $d$ number $1 + 2 + \dots + d = (\binom{d + 1}{2})$ , so the whole song delivers $\sum_{d = 1}^{12} (\binom{d + 1}{2}) = (\binom{14}{3}) = 364$ gifts, one for nearly every day of the year. The same sum says that a triangular pyramid of cannonballs ten layers high holds $(\binom{12}{3}) = 220$ balls.

Where the method stops

Look back at what every proof here did. Pascal's rule split committees into those with Ada and those without. The row sum split subsets by size, Vandermonde split committees by the number of mathematicians, and the hockey stick split subsets by their largest element. Each time the set was cut into pieces that did not overlap, and the sum rule added the pieces.

Many natural questions refuse to split cleanly. How many integers from $1$ to $100$ are divisible by $2$ or by $3$ ? There are $50$ multiples of $2$ and $33$ of $3$ , but adding them counts every multiple of $6$ twice, and the honest answer is $50 + 33 - 16 = 67$ . With three or four overlapping conditions the corrections pile up, and guessing them stops being safe. The next lesson turns that correction into an exact formula, inclusion and exclusion, and proves it by the method of this one: counting how many times each element is included.