7
$\begingroup$

The following combinatorial identity have been verified via maple, but I can not prove it. Who can prove it without WZ mehtod? $$\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose s}{s\choose m-s}$$.

$\endgroup$
6
$\begingroup$

Use subset-of-a-subset**, isolate non-index term, and then use Vandermonde*** to arrive at the result. $$\begin{align} \sum_{k=0}^s \color{blue}{\binom sk}\binom mk \color{blue}{\binom k{m-s}} &=\sum_{k=0}^{s}\color{blue}{\binom sk{\binom k{m-s}}} \binom mk \\ &=\sum_{k=0}^{s}\color{blue}{\binom s{m-s}\binom{2s-m}{k-m+s}}\binom mk\\ &=\binom s{m-s}\sum_{k=0}^{s}\binom{2s-m}{\color{red}k-m+s}\binom m{m\color{red}{-k}}\\ &=\binom s{m-s}\binom{2s}s \\&=\binom{2s}s\binom s{m-s}\qquad \blacksquare \end{align}$$


** Subset-of-a-subset: $$\color{blue}{\binom ab\binom bc=\binom ac \binom {a-c}{b-c}}$$

*** Vandermonde: $$\sum_{r=0}^{a-b} \binom a{\color{red}r+b} \binom c{d\color{red}{-r}}=\binom {a+c}{b+d}$$

$\endgroup$
  • $\begingroup$ very nice! Thank you! $\endgroup$ – Ji-Cai Liu Dec 13 '14 at 7:57
  • $\begingroup$ @Kevin - You're most welcome, and thank you! $\endgroup$ – hypergeometric Dec 13 '14 at 8:11
4
$\begingroup$

Let $n=m-s$; we may assume that $0\le n\le s$, as otherwise both sides are zero. The righthand side is the number of ordered pairs $\langle A,B\rangle$ such that $A$ is an $s$-subset of $[2s]$ and $B$ is an $m$-subset of $[s]$.

So is the lefthand side, though this is less obvious. Note that the $k$ term is zero unless $n\le k\le s$. For those $k$ we first pick $k$ elements of $[s]$ and then pick $n$ of those elements to be $B$. This leaves $k-n$ of the chosen elements unused; they will be $A\cap([s]\setminus B)$. The remaining

$$s-(k-n)=s+n-k=m-k$$

elements of $A$ must come from $B\cup([2s]\setminus[s])$, a set that has $s+n=m$ elements. Altogether there are

$$\binom{s}k\binom{k}n\binom{m}{m-k}=\binom{s}k\binom{k}n\binom{m}{k}$$

to complete the choice of $A$ and $B$ for this value of $k$, and summing over $k$ now yields the result.

$\endgroup$
  • $\begingroup$ The combinatorial proof is interesting,thank you! $\endgroup$ – Ji-Cai Liu Dec 13 '14 at 8:00
  • $\begingroup$ @Kevin: You're welcome. I tend to prefer them (when I manage to find them!). $\endgroup$ – Brian M. Scott Dec 13 '14 at 8:10
2
$\begingroup$

By way of enrichment here is another algebraic proof using basic complex variables.

Suppose we are trying to show that $$\sum_{k=0}^n {n\choose k} {m\choose k} {k\choose m-n} = {2n\choose n}{n\choose m-n}.$$

Introduce the integral representations $${m\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{k+1}} \; dz \quad\text{and}\quad {k\choose m-n} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^k}{w^{m-n+1}} \; dw.$$ where $m\ge n.$

This gives for the sum the representation $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{m-n+1}} \sum_{k=0}^n {n\choose k} \left(\frac{1+w}{z}\right)^k \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{m-n+1}} \frac{(1+w+z)^n}{z^n} \; dw \; dz.$$ Extracting the inner residue we obtain $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{n+1}} {n\choose m-n} (1+z)^{2n-m} \; dz \\ = {n\choose m-n} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \; dz \\ = {2n\choose n} {n\choose m-n}.$$

We have not made use of the properties of complex integrals here so this computation can also be presented using just algebra of generating functions.

There is a similar but somewhat more advanced calculation at this MSE link.

Apparently this method is due to Egorychev although some of it is probably folklore.

$\endgroup$
  • $\begingroup$ Very nice, your "by way of enrichment" solutions :) $\endgroup$ – hypergeometric Dec 13 '14 at 2:02
  • $\begingroup$ It is debatable whether one should write a new introduction for similar problems, I do copy from my previous posts sometimes when I write new ones, with the source already being present in my editor. $\endgroup$ – Marko Riedel Dec 13 '14 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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