Category: Combinatorics

Writing a Combinatorial Proof

This started life as a post on Quora, answering the question:

For any positive integer n, how do you write a combinatorial proof of the identity

\displaystyle {2n \choose n} = \sum_{i = 0}^{n} {n \choose i} {n \choose n-i}?

To write a combinatorial proof, the idea is to describe how each side of the equation is actually counting the same set of objects.

Now, if you have a set of 2n objects, \displaystyle {2n \choose n} (that is 2n choose n) is the number of subsets of that set which contain exactly n of them.

Now pretend that you’ve taken your 2n objects and put them into two boxes with n objects in each. Think about what each of your terms on the other side of the equation, \displaystyle {n \choose i}{n \choose n-i} represent. Then consider what you get when you add all of these together. You should be able to explain that this really does count the same thing as \displaystyle {2n \choose n}.

Now when I wrote the above, I wondered if this was a homework question someone had posted to Quora.  I didn’t fill in all the details since, while I’m happy to help someone with their homework, I don’t want to do it for them.

But in case anyone wants to see a worked out example, here’s the standard initial example of a combinatorial proof.  This is the identity that makes Pascal’s Triangle work as nicely as it does.

Theorem: \displaystyle {n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.

Proof: Let’s start by thinking about the expression on the left.  If we have a set with n objects in it, \displaystyle {n \choose k} is the number of ways we can select a subset of k objects.  To say that another way, it’s the number of ways we can pick k objects out of our set without caring what order they’re in.

Now suppose one of our objects has decided to wear a hat.  If we’re looking to select a subset with k objects, we can decide to include or exclude the one wearing the hat.

Say we don’t want to include the guy with the hat.  In that case, all k objects, have to be selected from the n-1 objects that aren’t wearing hats.  We can do this in \displaystyle {n-1 \choose k} different ways.

Now suppose we decide to include the one with the hat.  Well then, to get k objects altogether, we need to select k-1 more from the set.  There’s \displaystyle {n-1 \choose k-1} ways to get the rest of the objects that you need.

Putting these two together we see that \displaystyle {n-1 \choose k} + {n-1 \choose k-1} is also the number of ways to select a subset of k objects from a set containing n things.

Therefore, our identity must be true.

If you’d like to try one on your own, \displaystyle 2^n = \sum_{i = 0}^{n} {n \choose i} is another nice example.