Chu–Vandermonde identity

- binary linear code
- chord diagram
- combinatorial design
- graph
- Latin square
- matroid
- partition
- permutation
- shuffle
- tree
- Young diagram

category: combinatorics

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

$\sum_{j=0}^n \binom{x}{j} \binom{y}{n-j} = \binom{x+y}{n}$

in the polynomial ring $\mathbb{C}[x, y]$, where we recall $\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)$ ranging over $\mathbb{N} \times \mathbb{N}$ (as $\mathbb{N}^2$ is Zariski-dense in the affine plane $\mathbb{C}^2$). There one can resort to a structural proof or so-called “bijective proof”, where we count the number of $n$-element subsets $N$ of a finite set $P + Q$, with ${|P|} = p$ and ${|Q|} = q$. Regarding $P$ and $Q$ as subsets of the coproduct $P + Q$, if the subset $N \cap P$ of $P$ has $j$ elements, then the subset $N \cap Q$ of $Q$ has $n-j$ elements. The subset $N$ determines and is uniquely determined by the pair $(N \cap P, N \cap Q)$. The number of such pairs is $\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.