Is there a way to simplify : $\sum_{i=1}^{n} {n \choose i} {m \choose i}$?

  • $\begingroup$ If $m=n$, we get $\binom{2n}n$ $\endgroup$ – Simply Beautiful Art Mar 18 '17 at 12:39
  • $\begingroup$ What's the value of $m$? $\endgroup$ – Icycarus Mar 18 '17 at 12:40
  • 1
    $\begingroup$ @Icycarus what do you mean? m and n are random integers. $\endgroup$ – Nathan Mar 18 '17 at 12:42
  • $\begingroup$ @SimplyBeautifulArt whats about case $m \neq n$? $\endgroup$ – Nathan Mar 18 '17 at 12:44
  • 2
    $\begingroup$ @SimplyBeautifulArt You have seen it before, it is the Vandermonde convolution identity with the first term missing.$\sum_{i=1}^{n} \binom{n,i} \binom{m,i} =\binom{n+m,n}-1$ & it is very interesting IMHO :-) $\endgroup$ – Donald Splutterwit Mar 18 '17 at 13:02

When $n\leq m$ then $\sum_{k=0}^n \binom nk \binom m{k}$ counts all the ways to swap items between piles of $n$ and $m$ items; by doing counting selections of items in each pile to swap for each swap size ($k\in \{0..n\}$).   Also when $n>m$ it counts the same by the convention that $\binom {m}{r}=0$ for all $r>m$.

We could do this by gathering all the items into one pile of $n+m$ and count ways to sort them back into piles of $n$ and $m$ items.   This is $\binom {n+m}m$

Eg $\binom{5}2=10$

Thus as the count of ways to perform the same task must be the same:

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


NB: Your series is indexed $1$, so does not include the term $\binom n0\binom m0$ which is 1.

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

  • $\begingroup$ Awesome interpretation, thanks! $\endgroup$ – Nathan Mar 18 '17 at 13:35

prove with induction that we get $$\sum_{i=1}^n\binom{n}{i}\binom{m}{i}={\frac { \left( m+1 \right) \left( n+m \right) !}{ \left( m+1 \right) !\,n!}}-1 $$

  • $\begingroup$ Thanks, right side can be simplified to: $\frac{(n+m)!}{m!n!}-1 = {{n+m} \choose {m}} - 1$. I am wondering how you come up with this right side? $\endgroup$ – Nathan Mar 18 '17 at 12:58
  • $\begingroup$ i have this problem on my PC! i'm working with my students on combinatorics $\endgroup$ – Dr. Sonnhard Graubner Mar 18 '17 at 13:02
  • $\begingroup$ The result on your PC can simplify. $\endgroup$ – Claude Leibovici Mar 18 '17 at 13:04
  • $\begingroup$ ok i will note this thank you for the hint $\endgroup$ – Dr. Sonnhard Graubner Mar 18 '17 at 13:05
  • $\begingroup$ Is there a way to came to the right side if a have no idea about how it looks? $\endgroup$ – Nathan Mar 18 '17 at 13:07

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