# Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?

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.

-
This is Vandermonde's identity. A combinatorial proof is given at wikipedia and at proofwiki. See also this question: math.stackexchange.com/questions/76819 – Martin Sleziak Dec 14 '11 at 15:58
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$. – André Nicolas Dec 14 '11 at 16:23
Either of those could be posted as an answer. – joriki Dec 14 '11 at 17:14

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

-