4
$\begingroup$

A known identity of binomial coefficients is that $$ \sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}. $$ Is there a combinatorial proof/explanation of why it holds? Thanks.

$\endgroup$
  • 5
    $\begingroup$ This is Vandermonde's identity. A combinatorial proof is given at wikipedia and at proofwiki. See also this question: math.stackexchange.com/questions/76819 $\endgroup$ – Martin Sleziak Dec 14 '11 at 15:58
  • 6
    $\begingroup$ We have $m$ Martians and $n$ Neptunians, and want to select a crew of $j$ "people". The right side gives the number of ways. So does the left side, since we can choose $0$ Martians and $j$ Neptunians, or $1$ Martian and $j-1$ Neptunians or $\dots$. $\endgroup$ – André Nicolas Dec 14 '11 at 16:23
  • 1
    $\begingroup$ Either of those could be posted as an answer. $\endgroup$ – joriki Dec 14 '11 at 17:14
8
$\begingroup$

The captain of the pirate starship Free Enterprise finds $m$ Martians and $n$ Neptunians in a bar. In how many ways can she select a crew of $j$ creatures for a raid on Jupiter?

The right-hand side $\binom{m+n}{j}$ counts the number of ways to select $j$ creatures from the $m+n$ creatures available.

So does the left-hand side. For she could select $0$ Martians and $j$ Neptunians. This can be done in $\binom{m}{0}\binom{n}{j}$ ways.

Or else she could select $1$ Martian and $j-1$ Neptunians. This can be done in $\binom{m}{1}\binom{n}{j-1}$ ways.

Or else she could select $2$ Martians and $j-2$ Neptunians. This can be done in $\binom{m}{2}\binom{n}{j-2}$ ways.

And so on. Thus the number of ways to recruit $j$ creatures is given by the sum on the left-hand side.

Comment: The result, and the reasoning, remain correct even if, for example, $j>n$. All we need to do is to define $\binom{u}{v}$ to be $0$ if $u<v$.

$\endgroup$
1
$\begingroup$

What you need to prove is the Vandermonde's identity.

Vandermonde's Identity states that $\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r$, which can be proven combinatorially by noting that any combination of $r$ objects from a group of $m+n$ objects must have some $0\le k\le r$ objects from group $m$ and the remaining from group $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.