Vandermonde's identity
In combinatorics, Vandermonde's identity, or Vandermonde's convolution, named after Alexandre-Théophile Vandermonde (1772), states that
for binomial coefficients. This identity was given already in 1303 by the Chinese mathematician Zhu Shijie (Chu Shi-Chieh). See Askey 1975, pp. 59–60 for the history.
There is a q-analog to this theorem called the q-Vandermonde identity.
The general form of Vandermonde's identity is
In general, the product of two polynomials with degrees m and n, respectively, is given by
where we use the convention that ai = 0 for all integers i > m and bj = 0 for all integers j > n. By the binomial theorem,
Using the binomial theorem also for the exponents m and n, and then the above formula for the product of polynomials, we obtain
where the above convention for the coefficients of the polynomials agrees with the definition of the binomial coefficients, because both give zero for all i > m and j > n, respectively.
By comparing coefficients of xr, Vandermonde's identity follows for all integers r with 0 ≤ r ≤ m + n. For larger integers r, both sides of Vandermonde's identity are zero due to the definition of binomial coefficients.
Vandermonde's identity also admits a combinatorial double counting proof, as follows. Suppose a committee consists of m men and n women. In how many ways can a subcommittee of r members be formed? The answer is
The answer is also the sum over all possible values of k, of the number of subcommittees consisting of k men and r − k women:
Take a rectangular grid of r x (m+n-r) squares. There are
paths that start on the bottom left vertex and, moving only upwards or rightwards, end at the top right vertex (this is because r right moves and m+n-r up moves must be made (or vice versa) in any order, and the total path length is m+n). Call the bottom left vertex (0,0).
...
Wikipedia