Combinatorial Proofs

Section1.4Combinatorial Proofs

Investigate!9

The Stanley Cup is decided in a best of 7 tournament between two teams. In how many ways can your team win? Let's answer this question two ways:
1. How many of the 7 games does your team need to win? How many ways can this happen?
2. What if the tournament goes all 7 games? So you win the last game. How many ways can the first 6 games go down?
3. What if the tournament goes just 6 games? How many ways can this happen? What about 5 games? 4 games?
4. What are the two different ways to compute the number of ways your team can win? Write down an equation involving binomial coefficients (that is, \({n \choose k}\)'s). What pattern in Pascal's triangle is this an example of?
Generalize. What if the rules changed and you played a best of \(9\) tournament (5 wins required)? What if you played an \(n\) game tournament with \(k\) wins required to be named champion?

SubsectionPatterns in Pascal's Triangle

Have a look again at Pascal's triangle. Forget for a moment where it comes from. Just look at it as a mathematical object. What do you notice?

There are lots of patterns hidden away in the triangle, enough to fill a reasonably sized book. Here are just a few of the most obvious ones:

The entries on the border of the triangle are all 1.
Any entry not on the border is the sum of the two entries above it.
The triangle is symmetric. In any row, entries on the left side are mirrored on the right side.
The sum of all entries on a given row is a power of 2. (You should check this!)

We would like to state these observations in a more precise way, and then prove that they are correct. Now each entry in Pascal's triangle is in fact a binomial coefficient. The 1 on the very top of the triangle is \({0 \choose 0}\text{.}\) The next row (which we will call row 1, even though it is not the top-most row) consists of \({1 \choose 0}\) and \({1 \choose 1}\text{.}\) Row 4 (the row 1, 4, 6, 4, 1) consists of the binomial coefficients

\begin{equation*} {4 \choose 0} ~~ {4 \choose 1} ~~ {4 \choose 2} ~~ {4 \choose 3} ~~ {4 \choose 4}. \end{equation*}

Given this description of the elements in Pascal's triangle, we can rewrite the above observations as follows:

\({n \choose 0} = 1\) and \({n \choose n} = 1\text{.}\)
\({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{.}\)
\({n \choose k} = {n \choose n-k}\text{.}\)
\({n\choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n\text{.}\)

Each of these is an example of a binomial identity: an identity (i.e., equation) involving binomial coefficients.

Our goal is to establish these identities. We wish to prove that they hold for all values of \(n\) and \(k\text{.}\) These proofs can be done in many ways. One option would be to give algebraic proofs, using the formula for \({n \choose k}\text{:}\)

\begin{equation*} {n \choose k} = \frac{n!}{(n-k)!\,k!}. \end{equation*}

Here's how you might do that for the second identity above.

Example1.4.1

Give an algebraic proof for the binomial identity

\begin{equation*} {n \choose k} = {n-1\choose k-1} + {n-1 \choose k}. \end{equation*}

Solution

Proof

By the definition of \({n \choose k}\text{,}\) we have

\begin{equation*} {n-1 \choose k-1} = \frac{(n-1)!}{(n-1-(k-1))!(k-1)!} = \frac{(n-1)!}{(n-k)!(k-1)!} \end{equation*}

and

\begin{equation*} {n-1 \choose k} = \frac{(n-1)!}{(n-1-k)!k!}. \end{equation*}

Thus, starting with the right-hand side of the equation:

\begin{align*} {n-1 \choose k-1} + {n-1 \choose k} \amp = \frac{(n-1)!}{(n-k)!(k-1)!}+ \frac{(n-1)!}{(n-1-k)!\,k!}\\ \amp = \frac{(n-1)!k}{(n-k)!\,k!} + \frac{(n-1)!(n-k)}{(n-k)!\,k!}\\ \amp = \frac{(n-1)!(k+n-k)}{(n-k)!\,k!}\\ \amp = \frac{n!}{(n-k)!\, k!}\\ \amp = {n \choose k}. \end{align*}

The second line (where the common denominator is found) works because \(k(k-1)! = k!\) and \((n-k)(n-k-1)! = (n-k)!\text{.}\)

This is certainly a valid proof, but also is entirely useless. Even if you understand the proof perfectly, it does not tell you why the identity is true. A better approach would be to explain what \({n \choose k}\) means and then say why that is also what \({n-1 \choose k-1} + {n-1 \choose k}\) means. Let's see how this works for the four identities we observed above.

Example1.4.2

Explain why \({n \choose 0} = 1\) and \({n \choose n} = 1\text{.}\)

Solution

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).

Example1.4.3

Explain why \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{.}\)

Solution

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.

Example1.4.4

Prove the binomial identity \({n \choose k} = {n \choose n-k}\text{.}\)

Solution

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.

Example1.4.5

Prove the binomial identity \({n\choose 0} + {n \choose 1} + {n\choose 2} + \cdots + {n \choose n} = 2^n\text{.}\)

Solution

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).

Hopefully this gives some idea of how explanatory proofs of binomial identities can go. It is worth pointing out that more traditional proofs can also be beautiful. ³Most every binomial identity can be proved using mathematical induction, using the recursive definition for \({n \choose k}\text{.}\) We will discuss induction in Section 2.5. For example, consider the following rather slick proof of the last identity.

Expand the binomial \((x+y)^n\text{:}\)

\begin{equation*} (x + y)^n = {n \choose 0}x^n + {n \choose 1}x^{n-1}y + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x\cdot y^n + {n \choose n}y^n. \end{equation*}

Let \(x = 1\) and \(y = 1\text{.}\) We get:

\begin{equation*} (1 + 1)^n = {n \choose 0}1^n + {n \choose 1}1^{n-1}1 + {n \choose 2}1^{n-2}1^2 + \cdots + {n \choose n-1}1\cdot 1^n + {n \choose n}1^n. \end{equation*}

Of course this simplifies to:

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

Something fun to try: Let \(x = 1\) and \(y = 2\text{.}\) Neat huh?

SubsectionMore Proofs

The explanatory proofs given in the above examples are typically called combinatorial proofs. In general, to give a combinatorial proof for a binomial identity, say \(A = B\) you do the following:

Find a counting problem you will be able to answer in two ways.
Explain why one answer to the counting problem is \(A\text{.}\)
Explain why the other answer to the counting problem is \(B\text{.}\)

Since both \(A\) and \(B\) are the answers to the same question, we must have \(A = B\text{.}\)

The tricky thing is coming up with the question. This is not always obvious, but it gets easier the more counting problems you solve. You will start to recognize types of answers as the answers to types of questions. More often what will happen is you will be solving a counting problem and happen to think up two different ways of finding the answer. Now you have a binomial identity and the proof is right there. The proof is the problem you just solved together with your two solutions.

For example, consider this counting question:

How many 10-letter words use exactly four A's, three B's, two C's and one D?

Let's try to solve this problem. We have 10 spots for letters to go. Four of those need to be A's. We can pick the four A-spots in \({10 \choose 4}\) ways. Now where can we put the B's? Well there are only 6 spots left, we need to pick \(3\) of them. This can be done in \({6 \choose 3}\) ways. The two C's need to go in two of the 3 remaining spots, so we have \({3 \choose 2}\) ways of doing that. That leaves just one spot of the D, but we could write that 1 choice as \({1 \choose 1}\text{.}\) Thus the answer is:

\begin{equation*} {10 \choose 4}{6 \choose 3}{3 \choose 2}{1 \choose 1}. \end{equation*}

But why stop there? We can find the answer another way too. First let's decide where to put the one D: we have 10 spots, we need to choose 1 of them, so this can be done in \({10 \choose 1}\) ways. Next, choose one of the \({9 \choose 2}\) ways to place the two C's. We now have \(7\) spots left, and three of them need to be filled with B's. There are \({7 \choose 3}\) ways to do this. Finally the A's can be placed in \({4 \choose 4}\) (that is, only one) ways. So another answer to the question is

\begin{equation*} {10 \choose 1}{9 \choose 2}{7 \choose 3}{4 \choose 4}. \end{equation*}

Interesting. This gives us the binomial identity:

\begin{equation*} {10 \choose 4}{6 \choose 3}{3 \choose 2}{1 \choose 1} = {10 \choose 1}{9 \choose 2}{7 \choose 3}{4 \choose 4}. \end{equation*}

Here are a couple of other binomial identities with combinatorial proofs.

Example1.4.6

Prove the identity

\begin{equation*} 1 n + 2(n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = {n+2 \choose 3}. \end{equation*}

Solution

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.

Proof

Consider the question “How many 3-element subsets are there of the set \(\{1,2,3,\ldots, n+2\}\text{?}\)” We answer this in two ways:

Answer 1: We must select 3 elements from the collection of \(n+2\) elements. This can be done in \({n+2 \choose 3}\) ways.

Answer 2: Break this problem up into cases by what the middle number in the subset is. Say each subset is \(\{a,b,c\}\) written in increasing order. We count the number of subsets for each distinct value of \(b\text{.}\) The smallest possible value of \(b\) is \(2\text{,}\) and the largest is \(n+1\text{.}\)

When \(b = 2\text{,}\) there are \(1 \cdot n\) subsets: 1 choice for \(a\) and \(n\) choices (3 through \(n+2\)) for \(c\text{.}\)

When \(b = 3\text{,}\) there are \(2 \cdot (n-1)\) subsets: 2 choices for \(a\) and \(n-1\) choices for \(c\text{.}\)

When \(b = 4\text{,}\) there are \(3 \cdot (n-2)\) subsets: 3 choices for \(a\) and \(n-2\) choices for \(c\text{.}\)

And so on. When \(b = n+1\text{,}\) there are \(n\) choices for \(a\) and only 1 choice for \(c\text{,}\) so \(n \cdot 1\) subsets.

Therefore the total number of subsets is

\begin{equation*} 1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1)2 + n 1. \end{equation*}

Since Answer 1 and Answer 2 are answers to the same question, they must be equal. Therefore

\begin{equation*} 1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = {n+2 \choose 3}. \end{equation*}

Example1.4.7

Prove the binomial identity

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

Solution

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.

Proof

Consider the question: “How many pizzas can you make using \(n\) toppings when there are \(2n\) toppings to choose from?”

Answer 1: There are \(2n\) toppings, from which you must choose \(n\text{.}\) This can be done in \({2n \choose n}\) ways.

Answer 2: Divide the toppings into two groups of \(n\) toppings (perhaps \(n\) meats and \(n\) veggies). Any choice of \(n\) toppings must include some number from the first group and some number from the second group. Consider each possible number of meat toppings separately:

0 meats: \({n \choose 0}{n \choose n}\text{,}\) since you need to choose 0 of the \(n\) meats and \(n\) of the \(n\) veggies.

1 meat: \({n \choose 1}{n \choose n-1}\text{,}\) since you need 1 of \(n\) meats so \(n-1\) of \(n\) veggies.

2 meats: \({n \choose 2}{n \choose n-2}\text{.}\) Choose 2 meats and the remaining \(n-2\) toppings from the \(n\) veggies.

And so on. The last case is \(n\) meats, which can be done in \({n \choose n}{n \choose 0}\) ways.

Thus the total number of pizzas possible is

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

This is not quite the left-hand side … yet. Notice that \({n \choose n} = {n \choose 0}\) and \({n \choose n-1} = {n \choose 1}\) and so on, by the identity in Example 1.4.4. Thus we do indeed get

\begin{equation*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2. \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}. \end{equation*}

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. \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}. \end{equation*}

SubsectionExercises

1

Prove the identity \({n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\) using a question about subsets.

Solution

Proof

Question: How many subsets of size \(k\) are there of the set \(\{1,2,\ldots, n\}\text{?}\)

Answer 1: You must choose \(k\) out of \(n\) elements to put in the set, which can be done in \({n \choose k}\) ways.

Answer 2: First count the number of \(k\)-element subsets of \(\{1,2,\ldots, n\}\) which contain the number \(n\text{.}\) We must choose \(k-1\) of the \(n-1\) other element to include in this set. Thus there are \({n-1\choose k-1}\) such subsets. We have not yet counted all the \(k\)-element subsets of \(\{1,2,\ldots, n\}\) though. In fact, we have missed exactly those subsets which do NOT contain \(n\text{.}\) To form one of these subsets, we need to choose \(k\) of the other \(n-1\) elements, so this can be done in \({n-1 \choose k}\) ways. Thus the answer to the question is \({n-1 \choose k-1} + {n-1 \choose k}\text{.}\)

Since the two answers are both answers tot eh same question, they are equal, establishing the identity \({n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{.}\)

2

Give a combinatorial proof of the identity \(2+2+2 = 3\cdot 2\text{.}\)

Solution

Proof

Question: How many 2-letter words start with a, b, or c and end with either y or z?

Answer 1: There are two words that start with a, two that start with b, two that start with c, for a total of \(2+2+2\text{.}\)

Answer 2: There are three choices for the first letter and two choices for the second letter, for a total of \(3 \cdot 2\text{.}\)

Since the two answers are both answers to the same question, they are equal. Thus \(2 + 2 + 2 = 3\cdot 2\text{.}\)

3

Give a combinatorial proof for the identity \(1 + 2 + 3 + \cdots + n = {n+1 \choose 2}\text{.}\)

Solution

Proof

Question: How many subsets of \(A = {1,2,3, \ldots, n+1}\) contain exactly two elements?

Answer 1: We must choose 2 elements from \(n+1\) choices, so there are \({n+1 \choose 2}\) subsets.

Answer 2: We break this question down into cases, based on what the larger of the two elements in the subset is. The larger element can't be 1, since we need at least one element smaller than it.

Larger element is 2: there is 1 choice for the smaller element.

Larger element is 3: there are 2 choices for the smaller element.

Larger element is 4: there are 3 choices for the smaller element.

And so on. When the larger element is \(n+1\text{,}\) there are \(n\) choices for the smaller element. Since each two element subset must be in exactly one of these cases, the total number of two element subsets is \(1 + 2 + 3 + \cdots + n\text{.}\)

Answer 1 and answer 2 are both correct answers to the same question, so they must be equal. Therefore,

\begin{equation*} 1 + 2 + 3 + \cdots + n = {n+1 \choose 2} \end{equation*}

4

A woman is getting married. She has 15 best friends but can only select 6 of them to be her bridesmaids, one of which needs to be her maid of honor. How many ways can she do this?

What if she first selects the 6 bridesmaids, and then selects one of them to be the maid of honor?
What if she first selects her maid of honor, and then 5 other bridemaids?
Explain why \(6 {15 \choose 6} = 15 {14 \choose 5}\text{.}\)

Solution

She has \({15 \choose 6}\) ways to select the 6 bridesmaids, and then for each way, has 6 choices for the maid of honor. Thus she has \({15 \choose 6}6\) choices.
She has 15 choices for who will be her maid of honor. Then she needs to select 5 of the remaining 14 friends to be bridesmaids, which she can do in \({14 \choose 5}\) ways. Thus she has \(15 {14 \choose 5}\) choices.
We have answered the question (how many wedding parties can the bride choose from) in two ways. The first way gives the left-hand side of the identity and the second way gives the right-hand side of the identity. Therefore the identity holds.

5

Give a combinatorial proof of the identity \({n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}\text{.}\)

Solution

Proof

Question: You have a large container filled with ping-pong balls, all with a different number on them. You must select \(k\) of the balls, putting two of them in a jar and the others in a box. How many ways can you do this?

Answer 1: First select 2 of the \(n\) balls to put in the jar. Then select \(k-2\) of the remaining \(n-2\) balls to put in the box. The first task can be completed in \({n \choose 2}\) different ways, the second task in \({n-2 \choose k-2}\) ways. Thus there are \({n \choose 2}{n-2 \choose k-2}\) ways to select the balls.

Answer 2: First select \(k\) balls from the \(n\) in the container. Then pick 2 of the \(k\) balls you picked to put in the jar, placing the remaining \(k-2\) in the box. The first task can be completed in \({n \choose k}\) ways, the second task in \({k \choose 2}\) ways. Thus there are \({n \choose k}{k \choose 2}\) ways to select the balls.

Since both answers count the same thing, they must be equal and the identity is established.

6

Consider the bit strings in \(\B^6_2\) (bit strings of length 6 and weight 2).

How many of those bit strings start with 1?
How many of those bit strings start with 01?
How many of those bit strings start with 001?
Are there any other strings we have not counted yet? Which ones, and how many are there?
How many bit strings are there total in \(\B^6_2\text{?}\)
What binomial identity have you just given a combinatorial proof for?

Solution

After the 1, we need to find a 5-bit string with one 1. There are \({5 \choose 1}\) ways to do this.
\({4 \choose 1}\) strings (we need to pick 1 of the remaining 4 slots to be the second 1).
\({3 \choose 1}\) strings.
Yes. We still need strings starting with 0001 (there are \({2 \choose 1}\) of these) and strings starting 00001 (there is only \({1 \choose 1} = 1\) of these).
\({6 \choose 2}\) strings
An example of the Hockey Stick Theorem:
\begin{equation*} {1 \choose 1} + {2 \choose 1} + {3 \choose 1} + {4 \choose 1} + {5 \choose 1} = {6 \choose 2} \end{equation*}

7

Let's count ternary digit strings, that is, strings in which each digit can be 0, 1, or 2.

How many ternary digit strings contain exactly \(n\) digits?
How many ternary digit strings contain exactly \(n\) digits and \(n\) 2's.
How many ternary digit strings contain exactly \(n\) digits and \(n-1\) 2's. (Hint: where can you put the non-2 digit, and then what could it be?)
How many ternary digit strings contain exactly \(n\) digits and \(n-2\) 2's. (Hint: see previous hint)
How many ternary digit strings contain exactly \(n\) digits and \(n-k\) 2's.
How many ternary digit strings contain exactly \(n\) digits and no 2's. (Hint: what kind of a string is this?)
Use the above parts to give a combinatorial proof for the identity
\begin{equation*} {n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n. \end{equation*}

Solution

\(3^n\) strings, since there are 3 choices for each of the \(n\) digits.
\(1\) string, since all the digits need to be 2's. However, we might write this as \({n \choose 0}\) strings.
There are \({n \choose 1}\) places to put the non-2 digit. That digit can be either a 0 or a 1, so there are \(2{n \choose 1}\) such strings.
We must choose two slots to fill with 0's or 1's. There are \({n \choose 2}\) ways to do that. Once the slots are picked, we have two choices for the first slot (0 or 1) and two choices for the second slot (0 or 1). So there are a total of \(2^2{n \choose 2}\) such strings.
There are \({n \choose k}\) ways to pick which slots don't have the 2's. Then those slots can be filled in \(2^k\) ways (0 or 1 for each slot). So there are \(2^k{n \choose k}\) such strings.
These strings contain just 0's and 1's, so they are bit strings. There are \(2^n\) bit strings. But keeping with the pattern above, we might write this as \(2^n {n \choose n}\) strings.
We answer the question of how many length \(n\) ternary digit strings there are in two ways. First, each digit can be one of three choices, so the total number of strings is \(3^n\text{.}\) On the other hand, we could break the question down into cases by how many of the digits are 2's. If they are all 2's, then there are \({n \choose 0}\) strings. If all but one is a 2, then there are \(2{n \choose 1}\) strings. If all but 2 of the digits are 2's, then there are \(2^2{n \choose 2}\) strings. We choose 2 of the \(n\) digits to be non-2, and then there are 2 choices for each of those digits. And so on for every possible number of 2's in the string. Therefore \({n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n. \)

8

How many ways are there to rearrange the letters in the word “rearrange”? Answer this question in at least two different ways to establish a binomial identity.

Solution

The word contains 9 letters: 3 “r”s, 2 “a”s and 2 “e”s, along with an “n” and a “g”. We could first select the positions for the “r”s in \({9 \choose 3}\) ways, then the “a”s in \({6 \choose 2}\) ways, the “e”s in \({4 \choose 2}\) ways and then select one of the remaining two spots to put the “n” (placing the “g” in the last spot). This gives the answer

\begin{equation*} {9 \choose 3}{6 \choose 2}{4 \choose 2}{2\choose 1}{1\choose 1}. \end{equation*}

Alternatively, we could select the positions of the letters in the opposite order, which would give an answer

\begin{equation*} {9 \choose 1}{8\choose 1}{7 \choose 2}{5\choose 2}{3\choose 3}. \end{equation*}

(where the 3 “r”s go in the remaining 3 spots). These two expressions are equal:

\begin{equation*} {9 \choose 3}{6 \choose 2}{4 \choose 2}{2\choose 1}{1\choose 1} = {9 \choose 1}{8\choose 1}{7 \choose 2}{5\choose 2}{3\choose 3}. \end{equation*}

9

Give a combinatorial proof for the identity \(P(n,k) = {n \choose k}k!\)

Solution

Proof

Question: How many \(k\)-letter words can you make using \(n\) different letters without repeating any letter?

Answer 1: There are \(n\) choices for the first letter, \(n-1\) choices for the second letter, \(n-2\) choices for the third letter, and so on until \(n - (k-1)\) choices for the \(k\)th letter (since \(k-1\) letters have already been assigned at that point). The product of these numbers can be written \(\frac{n!}{(n-k)!}\) which is \(P(n,k)\text{.}\) Therefore there are \(P(n,k)\) words.

Answer 2: First pick \(k\) letters to be in the word from the \(n\) choices. This can be done in \({n \choose k}\) ways. Now arrange those letters into a word. There are \(k\) choices for the first letter, \(k-1\) choices for the second, and so on, for a total of \(k!\) arrangements of the \(k\) letters. Thus the total number of words is \({n \choose k}k!\text{.}\)

Since the two answers are correct answers to the same question, we have established that \(P(n,k) = {n \choose k}k!\text{.}\)

10

Establish the identity below using a combinatorial proof.

\begin{equation*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}. \end{equation*}

Solution

Proof

Question: How many 5-element subsets are there of the set \(\{1,2,\ldots, n+3\}\text{.}\)

Answer 1: We choose 5 out of the \(n+3\) elements, so \({n+3 \choose 5}\) subsets.

Answer 2: Break this up into cases by what the “middle” (third smallest) element of the 5 element subset is. The smallest this could be is a 3. In that case, we have \({2 \choose 2}\) choices for the numbers below it, and \({n \choose 2}\) choices for the numbers above it. Alternatively, the middle number could be a 4. In this case there are \({3 \choose 2}\) choices for the bottom two numbers and \({n-1 \choose 2}\) choices for the top two numbers. If the middle number is 5, then there are \({4 \choose 2}\) choices for the bottom two numbers and \({n-2 \choose 2}\) choices for the top two numbers. An so on, all the way up to the largest the middle number could be, which is \(n+1\text{.}\) In that case there are \({n \choose 2}\) choices for the bottom two numbers and \({2 \choose 2}\) choices for the top number. Thus the number of 5 element subsets is

\begin{equation*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2}. \end{equation*}

Since the two answers correctly answer the same question, we have

\begin{equation*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}. \end{equation*}