# 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 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.

• Dec 10, 2020 at 15:36