# Combinatorial proof of identity $\sum_{k=0}^{\min(a,b)}\binom{x+y+k}{k}\binom{x}{b-k}\binom{y}{a-k} = \binom{x+a}{b}\binom{y+b}{a}$

I try to make a combinatorial proof of the identity: $$\sum_{k=0}^{\min(a,b)}\binom{x+y+k}{k}\binom{x}{b-k}\binom{y}{a-k} = \binom{x+a}{b}\binom{y+b}{a}.$$

It is an exercise problem in Stanley's Enumerative Combinatorics (exercise 1.3 (d)). The answer in the book refers the article

G. E. Andrews, Identities in combinatorics I: on sorting two ordered sets, Discrete Math. 11 (1975), 97–106.

The article deals with similar, but not same identity. From the proofs in the article, I try to find the meaning of each term of LHS and RHS.

I guess the RHS of the identity counts the number of pair $(A,B)$ of subsets of $S = \{\alpha_x , \cdots, \alpha_1, \beta_1, \cdots, \beta_y\}$ (under ascending order) with $$A \subseteq \{\alpha_a , \cdots, \alpha_1, \beta_1, \cdots, \beta_y\},\, |A| = b,$$ $$B \subseteq \{\alpha_x , \cdots, \alpha_1, \beta_1, \cdots, \beta_b\},\, |B| = a.$$

However I can not get the meaning of each term of LHS (i.e. $\binom{x+y+k}{k}\binom{x}{b-k}\binom{y}{a-k}$) What is the meaning of it?

Am I going correct? If does, how to proceed the proof? There is another good proof of it? Thanks for any help.

## 1 Answer

Permit me to contribute an algebraic proof which in your case might make for interesting reading.

Suppose we seek to verify that $$\sum_{k=0}^{\min(a,b)} {x+y+k\choose k} {x\choose b-k} {y\choose a-k} = {x+a\choose b} {y+b\choose a}$$ where we take $y\ge a$ and $x\ge b.$

Observe that when we introduce the two integrals $${x\choose b-k} = {x\choose x-b+k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b-k+1}} \frac{1}{(1-z)^{x-b+k+1}} \; dz$$ and $${y\choose a-k} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{a-k+1}} (1+w)^y \; dw$$

we get automatic range control so we may extend $k$ to infinity to get for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} \frac{1}{(1-z)^{x-b+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{ (1+w)^y }{w^{a+1}} \\ \times \sum_{k\ge 0} {x+y+k\choose k} w^k \frac{z^k}{(1-z)^k} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} \frac{1}{(1-z)^{x-b+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{ (1+w)^y }{w^{a+1}} \\ \times \frac{1}{(1-wz/(1-z))^{x+y+1}} \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} (1-z)^{y+b} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{ (1+w)^y }{w^{a+1}} \\ \times \frac{1}{(1-z-wz)^{x+y+1}} \; dz \; dw.$$

The integral in $w$ is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{ (1+w)^y }{w^{a+1}} \sum_{q\ge 0} {x+y+q\choose q} z^q (1+w)^q \; dw \\ = \sum_{q\ge 0} {x+y+q\choose q} {y+q\choose a} z^q$$

which gives for the integral in $z$ $$\sum_{q\ge 0} {x+y+q\choose q} {y+q\choose a} {y+b\choose b-q} (-1)^{b-q}.$$

Note that $${y+b\choose b-q} {y+q\choose a} = \frac{(y+b)!}{(b-q)! (y+q)!} \frac{(y+q)!}{a! (y+q-a)!} \\ = \frac{(y+b)!}{(b-q)! (y+b-a)! } \frac{(y+b-a)!}{a! (y+q-a)!} \\ = {y+b\choose a} {y+b-a\choose b-q},$$

so we are done if we can show that $$\sum_{q\ge 0} {x+y+q\choose q} (-1)^{b-q} {y+b-a\choose b-q} = {x+a\choose b}.$$

To do this introduce $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{ (1+w)^{y+b-a} }{w^{b-q+1}} \; dw$$

which once more provides range control so we get for the sum $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{ (1+w)^{y+b-a} }{w^{b+1}} (-1)^b \sum_{q\ge 0} {x+y+q\choose q} (-1)^q w^q \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{ (1+w)^{y+b-a} }{w^{b+1}} (-1)^b \frac{1}{(1+w)^{x+y+1}} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{b+1}} (-1)^b \frac{1}{(1+w)^{x-b+a+1}} \; dw.$$

This yields $$(-1)^b (-1)^b {b+x-b+a\choose x-b+a} = {x+a\choose x-b+a} = {x+a\choose b}$$ as claimed.

This concludes the argument.