6
$\begingroup$

How do I evaluate $\sum_{k=0}^{n} {n \choose k}{m \choose k}$ for a given $n$ and $m$.

I have tried to use binomial expansion and combine factorials, but I have gotten nowhere. I don't really know how to start this problem.

The answer is ${n+m \choose n}$. Any help is greatly appreciated.

EDIT: I'm looking for a proof of this identity.

$\endgroup$
13
$\begingroup$

Use the fact that (which follows from the definition) $$\binom{m}{k}=\binom{m}{m-k}.$$ Once you have this the LHS can be written as $$LHS=\sum_{k=0}^n\binom{n}{k}\binom{m}{k}=\sum_{k=0}^n\binom{n}{k}\binom{m}{m-k}.$$

Now we can do a combinatorial argument to find this sum. Consider a group of $n$ men and $m$ women. We want to make a committee consisting of $m$ people. This can be done in any of the following ways:

1). $0$ men and $m$ women-----this selection can be made in $\binom{n}{0}\binom{m}{m}$ ways.

2). $1$ man and $m-1$ women-----this selection can be made in $\binom{n}{1}\binom{m}{m-1}$ ways.

and so on.....

m+1). $m$ men and $0$ women-----this selection can be made in $\binom{n}{m}\binom{m}{0}$ ways.

The sum total of this gives you the LHS. But this problem can also be solved by considering choosing $m$ people out of a group of $m+n$ people, which can be done in $\binom{n+m}{m}$ ways. Hence the two ways of counting should be equal.

$$\sum_{k=0}^n\binom{n}{k}\binom{m}{m-k}=\binom{n+m}{n}=\binom{n+m}{m}$$

$\endgroup$
  • $\begingroup$ This is a very nice solution. This is was I was looking for, thanks! $\endgroup$ – Vishwa Iyer Jul 3 '14 at 16:50
9
$\begingroup$

Using the Vandermonde Identity, this is $$ \sum_{k=0}^n\binom{n}{n-k}\binom{m}{k}=\binom{n+m}{n} $$


Proof of Vandermonde's Identity

$$ \begin{align} \sum_{k=0}^{m+n}\color{#C00000}{\binom{m+n}{k}}x^k &=(1+x)^{m+n}\tag{1}\\ &=(1+x)^m(1+x)^n\tag{2}\\ &=\sum_{j=0}^m\binom{m}{j}x^j\sum_{k=0}^n\binom{n}{k}x^k\tag{3}\\ &=\sum_{j=0}^m\sum_{k=j}^{n+j}\binom{m}{j}\binom{n}{k-j}x^k\tag{4}\\ &=\sum_{k=0}^{m+n}\color{#C00000}{\sum_{j=0}^k\binom{m}{j}\binom{n}{k-j}}x^k\tag{5} \end{align} $$ Explanation:
$(1)$: binomial theorem
$(2)$: property of exponents
$(3)$: binomial theorem
$(4)$: substitute $k\mapsto k-j$
$(5)$: change order of summation

Compare the coefficients of $x^k$.

$\endgroup$
  • $\begingroup$ Could you explain how this is possible? Like a proof? $\endgroup$ – Vishwa Iyer Jul 3 '14 at 16:34
  • $\begingroup$ I'm not really looking for an identity. $\endgroup$ – Vishwa Iyer Jul 3 '14 at 16:34
  • $\begingroup$ You need to be more specific, then. What do you need, the proof of the identity? $\endgroup$ – robjohn Jul 3 '14 at 16:37
  • $\begingroup$ I'm looking for a proof of the identity you just stated. $\endgroup$ – Vishwa Iyer Jul 3 '14 at 16:39
  • $\begingroup$ thank you for the nice solution, but I prefer Anurag's answer as it used a combinatorial argument and example, which is easier for me to understand. However, I still understood your solution and I appreciate it! $\endgroup$ – Vishwa Iyer Jul 3 '14 at 16:54
4
$\begingroup$

Building on robjohn's answer, to prove the Vandermonde identity look at the coefficient of $x^n$ on both sides of the equality $$ (x+1)^n(x+1)^m = (x+1)^{m+n}. $$

$\endgroup$
4
$\begingroup$

Suppose we want to pick $n$ children from a group of $n$ boys and $m$ girls. Then we can pick $n$ boys and $0$ girls, or $n - 1$ boys and $1 $ girl, or $n - 2$ boys and $2$ girls, ... There are

$$\sum_{r = 0}^n\binom{n}{n - r}\binom{m}{r} = \sum_{r = 0}^n\binom{n}{r}\binom{m}{r}$$

ways to do this.

But we can also look at it as choosing $n$ objects from a set of $n + m$ objects. Then there are

$$\binom{n + m}{n}$$

ways to do this.

Since both are counting the same number of things, they must be equal, i.e.

$$\sum_{r = 0}^n\binom{n}{r}\binom{m}{r} = \binom{n + m}{n}$$

$\endgroup$
4
$\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{\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]{\vphantom{\large A}\,#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} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\sum_{k=0}^{n}{n \choose k}{m \choose k}:\ {\large ?}}$

${\large\tt\mbox{Hereafter, I'll illustrate a general method:}}$

\begin{align}&\color{#66f}{\large\sum_{k=0}^{n}{n \choose k}{m \choose k}} =\sum_{k=0}^{n}{n \choose k}\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{m} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m} \over z}\, \sum_{k=0}^{n}{n \choose k}\pars{1 \over z}^{k}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m} \over z}\, \pars{1 + {1 \over z}}^{n}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m + n} \over z^{n + 1}}\, \,{\dd z \over 2\pi\ic} = \color{#66f}{\large{m + n \choose n}} \end{align}

$\endgroup$
  • $\begingroup$ +1, just because the use of contour integration in this situation made me laugh. $\endgroup$ – recursive recursion Jul 9 '14 at 23:02

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.