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.
Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?
4
$\begingroup$
combinatorics
summation
binomial-coefficients
combinatorial-proofs
-
5This is [Vandermonde's identity](http://en.wikipedia.org/wiki/Vandermonde%27s_identity). A combinatorial proof is given at wikipedia and at [proofwiki](http://www.proofwiki.org/wiki/Chu-Vandermonde_Identity). See also this question: http://math.stackexchange.com/questions/76819/ – 2011-12-14
-
6We 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$. – 2011-12-14
-
1Either of those could be posted as an answer. – 2011-12-14