2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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}}$ $\endgroup$
    – Ben Martin
    Commented Mar 14, 2023 at 5:54
  • 1
    $\begingroup$ Yes, it was. Sorry for that and thank you for your help :) $\endgroup$
    – thefool
    Commented Mar 14, 2023 at 6:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – FD_bfa
    Commented Mar 14, 2023 at 6:06

2 Answers 2

6
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .