Prove combinatorially that: $\displaystyle {{n}\choose{k}} {{n}\choose{m}} = \sum^{k}_{i=0} {{n}\choose{m+i}}{{m+i}\choose{k}} {{k}\choose{i}}$

Question

Prove combinatorially that: $$\displaystyle {{n}\choose{k}} {{n}\choose{m}} = \sum^{k}_{i=0} {{n}\choose{m+i}}{{m+i}\choose{k}} {{k}\choose{i}}$$

I couldn't solve it by myself. it's to complicated for me - judging by the RHS of the equation. Therefore I looked for a hint but had no luck. If anybody has seen that before - any help would be much appreciated.

Answer 1

Consider the problem of selecting two subsets of $\{1,2, \ldots, n \}$ The first one, $A$, having size $k$ and the second one, $B$, having size $m$. There are clearly ${{n}\choose{k}} {{n}\choose{m}}$ ways to do this. We wish to count this again in a different way to prove the given identity.

First we count the number of ways to chose such $A$ and $B$, but with the additional requirement that $|A \setminus B| = i$. We first can choose $A\cup B$. This is an arbitrary subset of $\{1,2, \ldots, n \}$ with $m +i$ elements, hence there are ${{n}\choose{m+i}}$ ways to choose that. From here we choose the elements of $A$ from $A\cup B$. There are ${{m+i}\choose{k}}$ ways to do this. Finally we choose $A \setminus B$ from $A$. There are ${{k}\choose{i}}$ ways to do this. Hence there are

$${{n}\choose{m+i}}{{m+i}\choose{k}}{{k}\choose{i}}$$

ways to pick $A$ and $B$ with $|A \setminus B| = i$. To finish we note that $i$ can be any integer from $0$ to $k$ and sum to get

$$\sum_{i= 0}^{k}{{n}\choose{m+i}}{{m+i}\choose{k}}{{k}\choose{i}}$$

This gives another method of counting

Answer 2

Hint: You can use the Vandermonde's Identity to get the answer.

\begin{split} \sum^{k}_{i=0} &{{n}\choose{m+i}}{{m+i}\choose{k}} {{k}\choose{i}}\\ &= \sum^{k}_{i=0} \frac{n!}{(m+i)!(n-m-i)!}\frac{(m+i)!}{k!(m+i-k)!}\frac{k!}{(k-i)i!}\\ &=\sum^{k}_{i=0} \frac{n!}{(n-m-i)!}\frac{1}{(m+i-k)!}\frac{1}{(k-i)i!}\\ &= \sum^{k}_{i=0} \frac{n!}{(n-m-i)!}\frac{m!}{(m+i-k)!(k-i)}\frac{1}{m!i!}\\ &= \sum^{k}_{i=0} {{m}\choose{k-i}}\frac{n!}{m!(n-m)!}\frac{(n-m)!}{(n-m-i)!i!}\\ &= \sum^{k}_{i=0} {{n}\choose{m}}{{m}\choose{k-i}} {{n-m}\choose{i}}\\ \end{split}

Notice that $\displaystyle\sum^{k}_{i=0} {{m}\choose{k-i}} {{n-m}\choose{i}}={{n}\choose{k}}$

So we have:$\displaystyle {{n}\choose{k}} {{n}\choose{m}} = \sum^{k}_{i=0} {{n}\choose{m+i}}{{m+i}\choose{k}} {{k}\choose{i}}$