Discrete Mathematics: An Open Introduction, 3rd edition

What do these binomial coefficients tell us? Well, \({n \choose 0}\) gives the number of ways to select 0 objects from a collection of \(n\) objects. There is only one way to do this, namely to not select any of the objects. Thus \({n \choose 0} = 1\text{.}\) Similarly, \({n \choose n}\) gives the number of ways to select \(n\) objects from a collection of \(n\) objects. There is only one way to do this: select all \(n\) objects. Thus \({n \choose n} = 1\text{.}\)

Alternatively, we know that \({n \choose 0}\) is the number of \(n\)-bit strings with weight 0. There is only one such string, the string of all 0's. So \({n \choose 0} = 1\text{.}\) Similarly \({n \choose n}\) is the number of \(n\)-bit strings with weight \(n\text{.}\) There is only one string with this property, the string of all 1's.

Another way: \({n \choose 0}\) gives the number of subsets of a set of size \(n\) containing 0 elements. There is only one such subset, the empty set. \({n \choose n}\) gives the number of subsets containing \(n\) elements. The only such subset is the original set (of all elements).

The easiest way to see this is to consider bit strings. \({n \choose k}\) is the number of bit strings of length \(n\) containing \(k\) 1's. Of all of these strings, some start with a 1 and the rest start with a 0. First consider all the bit strings which start with a 1. After the 1, there must be \(n-1\) more bits (to get the total length up to \(n\)) and exactly \(k-1\) of them must be 1's (as we already have one, and we need \(k\) total). How many strings are there like that? There are exactly \({n-1 \choose k-1}\) such bit strings, so of all the length \(n\) bit strings containing \(k\) 1's, \({n-1 \choose k-1}\) of them start with a 1. Similarly, there are \({n-1\choose k}\) which start with a 0 (we still need \(n-1\) bits and now \(k\) of them must be 1's). Since there are \({n-1 \choose k}\) bit strings containing \(n-1\) bits with \(k\) 1's, that is the number of length \(n\) bit strings with \(k\) 1's which start with a 0. Therefore \({n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\text{.}\)

Another way: consider the question, how many ways can you select \(k\) pizza toppings from a menu containing \(n\) choices? One way to do this is just \({n \choose k}\text{.}\) Another way to answer the same question is to first decide whether or not you want anchovies. If you do want anchovies, you still need to pick \(k-1\) toppings, now from just \(n-1\) choices. That can be done in \({n-1 \choose k-1}\) ways. If you do not want anchovies, then you still need to select \(k\) toppings from \(n-1\) choices (the anchovies are out). You can do that in \({n-1 \choose k}\) ways. Since the choices with anchovies are disjoint from the choices without anchovies, the total choices are \({n-1 \choose k-1}+{n-1 \choose k}\text{.}\) But wait. We answered the same question in two different ways, so the two answers must be the same. Thus \({n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\text{.}\)

You can also explain (prove) this identity by counting subsets, or even lattice paths.

Why is this true? \({n \choose k}\) counts the number of ways to select \(k\) things from \(n\) choices. On the other hand, \({n \choose n-k}\) counts the number of ways to select \(n-k\) things from \(n\) choices. Are these really the same? Well, what if instead of selecting the \(n-k\) things you choose to exclude them. How many ways are there to choose \(n-k\) things to exclude from \(n\) choices. Clearly this is \({n \choose n-k}\) as well (it doesn't matter whether you include or exclude the things once you have chosen them). And if you exclude \(n-k\) things, then you are including the other \(k\) things. So the set of outcomes should be the same.

Let's try the pizza counting example like we did above. How many ways are there to pick \(k\) toppings from a list of \(n\) choices? On the one hand, the answer is simply \({n \choose k}\text{.}\) Alternatively, you could make a list of all the toppings you don't want. To end up with a pizza containing exactly \(k\) toppings, you need to pick \(n-k\) toppings to not put on the pizza. You have \({n \choose n-k}\) choices for the toppings you don't want. Both of these ways give you a pizza with \(k\) toppings, in fact all the ways to get a pizza with \(k\) toppings. Thus these two answers must be the same: \({n \choose k} = {n \choose n-k}\text{.}\)

You can also prove (explain) this identity using bit strings, subsets, or lattice paths. The bit string argument is nice: \({n \choose k}\) counts the number of bit strings of length \(n\) with \(k\) 1's. This is also the number of bit string of length \(n\) with \(k\) 0's (just replace each 1 with a 0 and each 0 with a 1). But if a string of length \(n\) has \(k\) 0's, it must have \(n-k\) 1's. And there are exactly \({n\choose n-k}\) strings of length \(n\) with \(n-k\) 1's.

Let's do a “pizza proof” again. We need to find a question about pizza toppings which has \(2^n\) as the answer. How about this: If a pizza joint offers \(n\) toppings, how many pizzas can you build using any number of toppings from no toppings to all toppings, using each topping at most once?

On one hand, the answer is \(2^n\text{.}\) For each topping you can say “yes” or “no,” so you have two choices for each topping.

On the other hand, divide the possible pizzas into disjoint groups: the pizzas with no toppings, the pizzas with one topping, the pizzas with two toppings, etc. If we want no toppings, there is only one pizza like that (the empty pizza, if you will) but it would be better to think of that number as \({n \choose 0}\) since we choose 0 of the \(n\) toppings. How many pizzas have 1 topping? We need to choose 1 of the \(n\) toppings, so \({n \choose 1}\text{.}\) We have:

• Pizzas with 0 toppings: \({n \choose 0}\)
• Pizzas with 1 topping: \({n \choose 1}\)
• Pizzas with 2 toppings: \({n \choose 2}\)
• \(\vdots\)
• Pizzas with \(n\) toppings: \({n \choose n}\text{.}\)

The total number of possible pizzas will be the sum of these, which is exactly the left-hand side of the identity we are trying to prove.

Again, we could have proved the identity using subsets, bit strings, or lattice paths (although the lattice path argument is a little tricky).

To give a combinatorial proof we need to think up a question we can answer in two ways: one way needs to give the left-hand-side of the identity, the other way needs to be the right-hand-side of the identity. Our clue to what question to ask comes from the right-hand side: \({n+2 \choose 3}\) counts the number of ways to select 3 things from a group of \(n+2\) things. Let's name those things \(1, 2, 3, \ldots, n+2\text{.}\) In other words, we want to find 3-element subsets of those numbers (since order should not matter, subsets are exactly the right thing to think about). We will have to be a bit clever to explain why the left-hand-side also gives the number of these subsets. Here's the proof.

We will give two different proofs of this fact. The first will be very similar to the previous example (counting subsets). The second proof is a little slicker, using lattice paths.

For an alternative proof, we use lattice paths. This is reasonable to consider because the right-hand side of the identity reminds us of the number of paths from \((0,0)\) to \((n,n)\text{.}\)

Proof.

Consider the question: How many lattice paths are there from \((0,0)\) to \((n,n)\text{?}\)

Answer 1: We must travel \(2n\) steps, and \(n\) of them must be in the up direction. Thus there are \({2n \choose n}\) paths.

Answer 2: Note that any path from \((0,0)\) to \((n,n)\) must cross the line \(x + y = n\text{.}\) That is, any path must pass through exactly one of the points: \((0,n)\text{,}\) \((1,n-1)\text{,}\) \((2,n-2)\text{,}\) …, \((n, 0)\text{.}\) For example, this is what happens in the case \(n = 4\text{:}\)

How many paths pass through \((0,n)\text{?}\) To get to that point, you must travel \(n\) units, and \(0\) of them are to the right, so there are \({n \choose 0}\) ways to get to \((0,n)\text{.}\) From \((0,n)\) to \((n,n)\) takes \(n\) steps, and \(0\) of them are up. So there are \({n \choose 0}\) ways to get from \((0,n)\) to \((n,n)\text{.}\) Therefore there are \({n \choose 0}{n \choose 0}\) paths from \((0,0)\) to \((n,n)\) through the point \((0,n)\text{.}\)

What about through \((1,n-1)\text{.}\) There are \({n \choose 1}\) paths to get there (\(n\) steps, 1 to the right) and \({n \choose 1}\) paths to complete the journey to \((n,n)\) (\(n\) steps, \(1\) up). So there are \({n \choose 1}{n \choose 1}\) paths from \((0,0)\) to \((n,n)\) through \((1,n-1)\text{.}\)

In general, to get to \((n,n)\) through the point \((k,n-k)\) we have \({n \choose k}\) paths to the midpoint and then \({n \choose k}\) paths from the midpoint to \((n,n)\text{.}\) So there are \({n \choose k}{n \choose k}\) paths from \((0,0)\) to \((n,n)\) through \((k, n-k)\text{.}\)

All together then the total paths from \((0,0)\) to \((n,n)\) passing through exactly one of these midpoints is

\begin{equation*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2\text{.} \end{equation*}

Since these two answers are answers to the same question, they must be equal, and thus

\begin{equation*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2 = {2n \choose n}\text{.} \end{equation*}