11.4: Combinatorial Proofs
- Last updated
- Sep 29, 2021
- Save as PDF
- Page ID
- 86171
( \newcommand{\kernel}{\mathrm{null}\,}\)
Investigate!
- 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:
- How many of the 7 games does your team need to win? How many ways can this happen?
- What if the tournament goes all 7 games? So you win the last game. How many ways can the first 6 games go down?
- What if the tournament goes just 6 games? How many ways can this happen? What about 5 games? 4 games?
- 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,
's). What pattern in Pascal's triangle is this an example of?
- Generalize. What if the rules changed and you played a best of
tournament (5 wins required)? What if you played an game tournament with wins required to be named champion?
Patterns 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
Given this description of the elements in Pascal's triangle, we can rewrite the above observations as follows:
and . . . .
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
Here's how you might do that for the second identity above.
Example
Give an algebraic proof for the binomial identity
- Solution
-
Proof
By the definition of
, we haveand
Thus, starting with the right-hand side of the equation:
The second line (where the common denominator is found) works because
and .
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
Example
Explain why
- Solution
-
What do these binomial coefficients tell us? Well,
gives the number of ways to select 0 objects from a collection of objects. There is only one way to do this, namely to not select any of the objects. Thus . Similarly, gives the number of ways to select objects from a collection of objects. There is only one way to do this: select all objects. Thus .Alternatively, we know that
is the number of -bit strings with weight 0. There is only one such string, the string of all 0's. So . Similarly is the number of -bit strings with weight . There is only one string with this property, the string of all 1's.Another way:
gives the number of subsets of a set of size containing 0 elements. There is only one such subset, the empty set. gives the number of subsets containing elements. The only such subset is the original set (of all elements).
Example
Explain why
- Solution
-
The easiest way to see this is to consider bit strings.
is the number of bit strings of length containing 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 more bits (to get the total length up to ) and exactly of them must be 1's (as we already have one, and we need total). How many strings are there like that? There are exactly such bit strings, so of all the length bit strings containing 1's, of them start with a 1. Similarly, there are which start with a 0 (we still need bits and now of them must be 1's). Since there are bit strings containing bits with 1's, that is the number of length bit strings with 1's which start with a 0. Therefore .Another way: consider the question, how many ways can you select
pizza toppings from a menu containing choices? One way to do this is just . 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 toppings, now from just choices. That can be done in ways. If you do not want anchovies, then you still need to select toppings from choices (the anchovies are out). You can do that in ways. Since the choices with anchovies are disjoint from the choices without anchovies, the total choices are . But wait. We answered the same question in two different ways, so the two answers must be the same. Thus .You can also explain (prove) this identity by counting subsets, or even lattice paths.
Example
Prove the binomial identity
- Solution
-
Why is this true?
counts the number of ways to select things from choices. On the other hand, counts the number of ways to select things from choices. Are these really the same? Well, what if instead of selecting the things you choose to exclude them. How many ways are there to choose things to exclude from choices. Clearly this is as well (it doesn't matter whether you include or exclude the things once you have chosen them). And if you exclude things, then you are including the other 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
toppings from a list of choices? On the one hand, the answer is simply . Alternatively, you could make a list of all the toppings you don't want. To end up with a pizza containing exactly toppings, you need to pick toppings to not put on the pizza. You have choices for the toppings you don't want. Both of these ways give you a pizza with toppings, in fact all the ways to get a pizza with toppings. Thus these two answers must be the same: .You can also prove (explain) this identity using bit strings, subsets, or lattice paths. The bit string argument is nice:
counts the number of bit strings of length with 1's. This is also the number of bit string of length with 0's (just replace each 1 with a 0 and each 0 with a 1). But if a string of length has 0's, it must have 1's. And there are exactly strings of length with 1's.
Example
Prove the binomial identity
- Solution
-
Proof
Let's do a “pizza proof” again. We need to find a question about pizza toppings which has
as the answer. How about this: If a pizza joint offers 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
. 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
Pizzas with 0 toppings: since we choose 0 of the toppings. How many pizzas have 1 topping? We need to choose 1 of the toppings, so . We have: Pizzas with 1 topping: Pizzas with 2 toppings: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).
- Pizzas with
toppings: .
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. 3 Most every binomial identity can be proved using mathematical induction, using the recursive definition for
Expand the binomial
Let
Of course this simplifies to:
Something fun to try: Let
More 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
- Find a counting problem you will be able to answer in two ways.
- Explain why one answer to the counting problem is
. - Explain why the other answer to the counting problem is
.
Since both
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
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
Interesting. This gives us the binomial identity:
Here are a couple of other binomial identities with combinatorial proofs.
Example
Prove the identity
- 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:
counts the number of ways to select 3 things from a group of things. Let's name those things . 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
” We answer this in two ways:Answer 1: We must select 3 elements from the collection of
elements. This can be done in ways.Answer 2: Break this problem up into cases by what the middle number in the subset is. Say each subset is
written in increasing order. We count the number of subsets for each distinct value of . The smallest possible value of is , and the largest is .When
, there are subsets: 1 choice for and choices (3 through ) for .When
, there are subsets: 2 choices for and choices for .When
, there are subsets: 3 choices for and choices for .And so on. When
, there are choices for and only 1 choice for , so subsets.Therefore the total number of subsets is
Since Answer 1 and Answer 2 are answers to the same question, they must be equal. Therefore
Example
Prove the binomial identity
- Solution 1
-
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
toppings when there are toppings to choose from?”Answer 1: There are
toppings, from which you must choose . This can be done in ways.Answer 2: Divide the toppings into two groups of
toppings (perhaps meats and veggies). Any choice of 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:
, since you need to choose 0 of the meats and of the veggies.1 meat:
, since you need 1 of meats so of veggies.2 meats:
. Choose 2 meats and the remaining toppings from the veggies.And so on. The last case is
meats, which can be done in ways.Thus the total number of pizzas possible is
This is not quite the left-hand side … yet. Notice that
and and so on, by the identity in Example 1.4.4. Thus we do indeed getSince these two answers are answers to the same question, they must be equal, and thus
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
to .Proof
Consider the question: How many lattice paths are there from
toAnswer 1: We must travel
steps, and of them must be in the up direction. Thus there are paths.Answer 2: Note that any path from
to must cross the line . That is, any path must pass through exactly one of the points: , , , …, . For example, this is what happens in the case
How many paths pass through
What about through
In general, to get to
All together then the total paths from
Since these two answers are answers to the same question, they must be equal, and thus