More Bijections!

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


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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s