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.

  • 5
    This 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
  • 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$.2011-12-14
  • 1
    Either of those could be posted as an answer.2011-12-14

2 Answers 2