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

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.

• Is there a typo? I think it should be $\displaystyle {{n}\choose{k}} {{n}\choose{m}} = \sum^{k}_{i=0} {{n}\choose{m+i}}{{m+i}\choose{k}} {{k}\choose{i}}$ Commented Mar 14, 2023 at 5:54
• Yes, it was. Sorry for that and thank you for your help :) Commented Mar 14, 2023 at 6:00
• You should edit your question to let us know what you have already tried. You mentioned that you had a hint. Maybe we could explain the hint to you if you edit the post to include what it says. Commented Mar 14, 2023 at 6:06

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

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

• I don't think that's what was meant by a "combinatorial argument". Commented Mar 14, 2023 at 12:42
• @DavidK Sorry about that, but I think it may be also useful to someone else. Commented Mar 14, 2023 at 14:10