5
$\begingroup$

Evaluate the following sum using a combinatorial argument:

$$ \sum\limits_{k=0}^n {n \choose k} {m \choose k} $$

Can someone push me in the right direction with this? I thought for combinatorial proofs there has to be a left side and a right side where one side can be used to form a question? (if that makes sense? haha)

Is there a difference with combinatorial arguments? Any help would be greatly appreciated.

$\endgroup$
  • $\begingroup$ You are supposed to find the right hand side yourself :) $\endgroup$ – darij grinberg Feb 24 '15 at 20:12
  • $\begingroup$ Is $m$ a constant, or is it somehow related to $n$? $\endgroup$ – Théophile Feb 24 '15 at 20:13
  • $\begingroup$ There is nothing saying that it is related to n in anyways, so I am assuming it is a constant. $\endgroup$ – MathyMatherson Feb 24 '15 at 20:16
  • $\begingroup$ I think we can assume $m \ge n$, so that the problem makes sense. $\endgroup$ – DanielV Feb 24 '15 at 20:20
  • $\begingroup$ Try a few examples: choose $n=3$, say, and try different values for $m$. Do you see the pattern? $\endgroup$ – Théophile Feb 24 '15 at 20:20
3
$\begingroup$

As darij grinberg said in the comments, you’ll have to find the other side of the identity yourself; it’s a closed form, not a summation.

HINT: You may find it easier to come up with a combinatorial interpretation of the summation if you rewrite it as

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

$\endgroup$

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