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 to 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 the 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 it does, how to proceed with the proof? There is another good proof of it? Thanks for any help.



Your Answer

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

Browse other questions tagged or ask your own question.