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.


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.


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.