Tag Archives: binomial coefficients

More Bijections!

Posted on by

You can imagine that I’m really bored as I’m writing another blog post given I just wrote one yesterday. Anyhow, some more identities, with some more proofs. This post will be one of the most brusque posts I’ve ever written; so yes, you can blame me if you can’t understand parts of the post. (Yes, you may comment and I’ll respond, I promise.)

Behold!

\displaystyle \sum_{i=0}^{n} \dbinom{x}{i} \dbinom{y}{n-i} = \dbinom{x+y}{n}

Assume there is a class of x boys and y girls. (No, you may not assume x = y and that every girl/boy has a boy/girlfriend.) Now, you’re to pick n out of the class to go for a movie. The right hand side simply counts the number as a binomial coefficient without distinguishing between boys and girls. The left hand side, being a sexist, distinguishes between boys and girls, and picks i boys first, and then n-i girls for the picnic. Using the addition principle, the left hand side (sexist sod) counts the number of ways to take a total of n boys and girls for the movie.

Now that you’re bored watching the stupid movie, why not try another combinatorial identity? Yes, this one is a bit tricky. I always like the tricky ones.

\displaystyle \sum_{i=0}^{m} \dbinom{n+i}{i} = \dbinom{n+m+1}{m}

Consider the scenario where you have n +m+1 girls standing in a queue (or a stack or even a list). You are to pick, well, m girls out of the given n+m+1 for another movie this time. Again, the right hand side is the straightforward answer. The left hand side counts the same quantity, evaluated in a slightly complex way. We look at the largest continuous set of girls we’ve selecting starting from the first one. We can select at most m in this continuous string, or none at all. We select the first m-i (note 0 \le i \le m) girls, skip the (m-i+1)^{\mathrm{th}} girl (as we select the longest continuous string), and select the remaining i girls from the remaining n + m + 1 - (m - i) - 1 = n + i (removing the selected the first m-i, and rejected (m-i+1)^{\mathrm{th}} girl). Applying the addition principle on this evaluation simply yields the result.

Football! (And we need a captain this time.)

\displaystyle \sum_{i=0}^{n} i \dbinom{n}{i} = n2^{n-1}

This is one of my favourite identities among those which have a very simple bijective proof. Consider selecting a football team out of n boys with a captain. One way to count the number of possible teams is to select an arbitrarily sized team, and then select the captain out of the chosen ones. The left hand side simply counts this number. Another way to evaluate the same number would be to select the captain first, which can be done in n ways, and then select the remaining team, which can be done in 2^{n-1} ways (as you may either select a player, or reject him). And voila!

Boom! (Just wanted to end this post with a blast.)

PS The promised exercise for my devout readers is to prove the following identity.

\displaystyle \sum_{i=0}^{n} i^2 \dbinom{n}{i} = n(n+1)2^{n-2}

PPS You might want a goalkeeper on your team to save a goal from the identity above.

Bijections!

Posted on by

Hello, imaginary reader! Long time, no see. It’s okay, I prefer rooks anyway. Now that I’ve started with a lame unoriginal joke you probably didn’t understand, I can continue with the core matter of this post which I’ve wanted to do for a long long (exponential) time. Proving combinatorial identities with bijections! This post is going to be somewhat terse, as that is the point of proving an identity bijectively.

I presume one knows what binomial coefficients mean bijectively, and some basic combinatorial principles like addition and multiplication principle. I’ll be a bit more explanative in the starting few examples, after which I’ll just, well, be lazy and write a few words which should be enough, given sufficient time, for one to understand.

So, here goes.

\displaystyle \sum_{i=0}^{n} \dbinom{n}{i} = 2^n

The left side counts the subsets of size i of a set of size n where i ranges from 0 to n. In particular, the left counts all the subsets of the set in reference by addition principle; whereas the right side counts all the subsets of the set in reference by multiplication principle, as each element of the set has 2 choices, either to be included in a subset, or not.

Moving on.

\displaystyle \sum_{i=0}^{n} (-1)^n \dbinom{n}{i} = 0

Okay, I’ll cheat a bit here. I won’t directly equate the left and right sides of the above identity, but make the “clever” and obvious observation that it is equivalent to proving that the number of odd sized subsets of a set, and the number of even sized subsets of a set are equal. The proof is surprisingly simple. Fix any arbitrary element a from the set, and any arbitrary subset A of the given set. If A contains a, remove a from A to get a new set A' of the opposite parity. If A does not contain a, then add a to A to get a new set A' of the opposite parity. I’ll leave it to you to verify that this gives a bijection between subsets of a set with even parity and subsets of a set with odd parity.

Simple enough.

\displaystyle \dbinom{n-1}{i} + \dbinom{n-1}{i-1} = \dbinom{n}{i}

Let’s play football now! The right hand side simply counts the ways of choosing i players from a total of n for the starting squad. Now, for the left hand side, fix an arbitrary player p. If you pick p, then you’re left with n-1 players and have to pick i-1 out of them. On the other hand, if you don’t pick p, you’re left with n-1 players, and have to pick i out of them. The sum of these two, is the left hand side, and by the addition principle, equal to the number of ways of choosing i players from n, the right hand side, as desired.

And we’re done.

As you know the number of lazy bones I have is 207, I’ll stop right here.

Anyhow, I plan to convert this post into a series of posts on bijective identities, with three identities with bijective proofs, and one identity to be left to be proven by the lovely imaginary readers of my blog. Happy solving!

\displaystyle 2 \dbinom{2n-1}{n} = \dbinom{2n}{n}