Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
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
6  
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
1  
Either of those could be posted as an answer. –  joriki Dec 14 '11 at 17:14
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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