Vandermonde's Identity

m+nr = _k mk nr-k — split the committee by team.

The idea

Theorem (Vandermonde's identity).

For all non-negative integers $m$, $n$ and $r$, $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}.$

Both sides count committees. The left side counts the committees of $r$ people that can be formed from a club of $m+n$ members; a committee is a set, so the order of choosing never enters. The right side counts the same committees after the club has been split into two groups, of sizes $m$ and $n$, and each committee has been sorted by the number $k$ of members it draws from the first group. The identity says that sorting the committees into these classes does not change how many there are.

Ways to work on it

• Walkthrough. Discover the identity by double-counting committees drawn from two groups, then check it on a small case.
• Proof. See why — double-count one set of committees two ways: directly, and split by how many women it has.
• Practice. Apply Vandermonde's identity to collapse a sum of binomial products into a single coefficient.
• Hardest. Decide which binomial identity a given sum is an instance of.

Not sure where to start? Take the ten-question placement test.