nLab
Chu–Vandermonde identity

The Chu-Vandermonde identity is a basic identity in the combinatorics of binomial coefficients. It can be summarized as a polynomial identity

j=0 n(xj)(ynj)=(x+yn)\sum_{j=0}^n \binom{x}{j} \binom{y}{n-j} = \binom{x+y}{n}

in the polynomial ring [x,y]\mathbb{C}[x, y], where we recall (xk)=x k̲k!x(x1)(xk+1)k!\binom{x}{k} = \frac{x^{\underline{k}}}{k!} \coloneqq \frac{x (x-1) \ldots (x - k + 1)}{k!}.

To prove it, it suffices to verify it for the values (x,y)=(p,q)(x, y) = (p, q) ranging over ×\mathbb{N} \times \mathbb{N} (as 2\mathbb{N}^2 is Zariski-dense in the affine plane 2\mathbb{C}^2). There one can resort to a structural proof or so-called “bijective proof”, where we count the number of nn-element subsets NN of a finite set P+QP + Q, with |P|=p{|P|} = p and |Q|=q{|Q|} = q. Regarding PP and QQ as subsets of the coproduct P+QP + Q, if the subset NPN \cap P of PP has jj elements, then the subset NQN \cap Q of QQ has njn-j elements. The subset NN determines and is uniquely determined by the pair (NP,NQ)(N \cap P, N \cap Q). The number of such pairs is j=0 n(pj)(qnj)\sum_{j=0}^n \binom{p}{j} \binom{q}{n-j}, exactly as claimed.

(Structurally, we are relying on the fact that the category of finite sets is an extensive category.)

There is more to be written on this in terms of species, coalgebras, etc.

Last revised on August 26, 2018 at 08:17:15. See the history of this page for a list of all contributions to it.