Combinatorial Proof Question: Vandermonde convolution identity I'm really iffy on combinatorial proofs in general and now that there is a sum, it's just confused me even more. Can someone try and walk me through this proof?
$$
\binom{m + n}{r} = \sum_{k=0}^r \binom{m}{k}\binom{n}{r - k}
$$
 A: There are $m$ men and $n$ women, and you need to pick a team of $r$ people.  The LHS counts how many ways to do this directly, the RHS breaks this down into $k$ men and $r-k$ women.
A: $\newcommand{\+}{^{\dagger}}%
 \newcommand{\angles}[1]{\left\langle #1 \right\rangle}%
 \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}%
 \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}%
 \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}%
 \newcommand{\dd}{{\rm d}}%
 \newcommand{\down}{\downarrow}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}%
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}%
 \newcommand{\fermi}{\,{\rm f}}%
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}%
 \newcommand{\half}{{1 \over 2}}%
 \newcommand{\ic}{{\rm i}}%
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}%
 \newcommand{\isdiv}{\,\left.\right\vert\,}%
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}%
 \newcommand{\ol}[1]{\overline{#1}}%
 \newcommand{\pars}[1]{\left( #1 \right)}%
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}%
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}%
 \newcommand{\sech}{\,{\rm sech}}%
 \newcommand{\sgn}{\,{\rm sgn}}%
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}%
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{{m + n \choose r} = \sum_{k=0}^{r}{m \choose k}{n \choose r - k}:\ {\large ?}}$.
Since $\ds{{n \choose r - k} = 0\ \mbox{when}\ k > r}$, we'll have
$\ds{{m + n \choose r} = \sum_{k=0}^{m}{m \choose k}{n \choose r - k}}$

\begin{align}
\color{#00f}{\large\sum_{k=0}^{r}{m \choose k}{n \choose r - k}}&=
\sum_{k=0}^{m}{m \choose k}\sum_{\ell = 0}^{n}{n \choose \ell}\delta_{\ell, r - k}
=
\sum_{k=0}^{m}{m \choose k}\sum_{\ell = 0}^{n}{n \choose \ell}
\int_{\verts{z} = 1}{1 \over z^{\ell - r + k + 1}}\,{\dd z \over 2\pi\ic}
\\[3mm]&=
\int_{\verts{z} = 1}\bracks{\sum_{k=0}^{m}{m \choose k}\pars{1 \over z}^{k}}
\bracks{\sum_{\ell = 0}^{n}{n \choose \ell}\pars{1 \over z}^{\ell}}
{1 \over z^{-r + 1}}\,{\dd z \over 2\pi\ic}
\\[3mm]&=
\int_{\verts{z} = 1}\pars{1 + {1 \over z}}^{m}
\pars{1 + {1 \over z}}^{n}\,{1 \over z^{-r + 1}}\,{\dd z \over 2\pi\ic}
=
\int_{\verts{z} = 1}
{\pars{1 + z}^{m + n} \over z^{m + n - r + 1}}\,{\dd z \over 2\pi\ic}
\\[3mm]&=
\sum_{\ell = 0}^{m + n}{m + n \choose \ell}\int_{\verts{z} = 1}
{z^{\ell} \over z^{m + n - r + 1}}\,{\dd z \over 2\pi\ic}
=
\sum_{\ell = 0}^{m + n}{m + n \choose \ell}\delta_{\ell,m + n - r}
\\[3mm]&={m + n \choose m + n - r}
=\color{#00f}{\large{m + n \choose r}}
\end{align}

