3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ $$(1+x)^{m+n}=(1+x)^m(1+x)^n$$ $\endgroup$ – Lucian Feb 11 '14 at 0:28
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The LHS is pretty clear to me. It's unclear to me how the RHS breaks it down though. The sum is what is throwing me off. $\endgroup$ – user127778 Feb 10 '14 at 23:43
  • $\begingroup$ Consider, say, $k=3$. Then ${m\choose 3}$ chooses three men, and ${n\choose r-3}$ chooses $r-3$ women. We multiply because those two choices are independent. $\endgroup$ – vadim123 Feb 10 '14 at 23:44
1
$\begingroup$

$\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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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