5
$\begingroup$

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.

$\endgroup$
1

0

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.