# Vandermonde's identity

In combinatorial mathematics, Vandermonde's identity, named after [[Alexandre-Th�ophile Vandermonde]], states that

${n+m \choose r}=\sum_{k=0}^r{n \choose k}{m \choose r-k}.$

This may be proved by simple algebra relying on the fact that

${n \choose k}={n! \over k!(n-k)!},$

(see factorial) but it also admits a more combinatorics-flavored bijective proof, as follows. Suppose a committee in the Senate consists of n Democrats and m Republicans. In how many ways can a subcommittee of r members be formed? The answer is of course

${n+m \choose r}.$

But on the other hand, the answer is the sum over all possible values of k, of the number of subcommittees consisting of k Democrats and rk Republicans.

When both sides have been divided by the expression on the left, so that the sum is 1, then the terms of the sum may be interpreted as probabilities. The resulting probability distribution is the hypergeometric distribution. Suppose one chooses a subcommittee of r members randomly from the aforementioned subcommittee. What then is the probability that the number of Democrats on the subcommittee is k? The answer is the appropriate term in the sum.