范德蒙恒等式

证明

组合方法

甲班有 m 个同学，乙班有 n 个同学，从两个班中选出 k 个同学有 （公式略） 种方法。

从甲班选 k-i 名，从乙班选 i 名有 （公式略） 种方法，考虑所有情况 i=0,1,…,k，从两个班中合计 k 选出个同学有 （公式略） 种方法。

所以 （公式略）

母函数方法

• 注意到 (1+x)ⁿ(1+x)^(m)=(1+x)^(n+m)
• 等号左边化简成 （公式略）
• 等号右边则根据定义 （公式略）
• 比较 x^(k) 系数，可得 （公式略）

推广

多变量型： （公式略）

其中 （公式略）

展开 (x₁+x₂+… +xₜ)ⁿ₁+n₂+… +nₛ=(x₁+x₂+… +xₜ)ⁿ₁… (x₁+x₂+… +xₜ)ⁿₛ 可得以上结论。

超几何函数

• 范德蒙恒等式是超几何函数的一个整数特例。 （公式略）
• ∑ （公式略）
• = （公式略）

In combinatorics, Vandermonde's identity (or Vandermonde's convolution) is the following identity for binomial coefficients: （公式略）

for any nonnegative integers r, m, n. The identity is named after Alexandre-Théophile Vandermonde (1772), although it was already known in 1303 by the Chinese mathematician Zhu Shijie.

There is a q-analog to this theorem called the q-Vandermonde identity.

Vandermonde's identity can be generalized in numerous ways, including to the identity （公式略）

Proofs

Algebraic proof

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 x r, 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.

Combinatorial proof

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: （公式略）

Geometrical proof

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

There are （公式略） paths starting at (0, 0) that end at (k, m−k), as k right moves and m−k upward moves must be made (and the path length is m). Similarly, there are （公式略） paths starting at (k, m−k) that end at (r, m+n−r), as a total of r−k right moves and (m+n−r) − (m−k) upward moves must be made and the path length must be r−k + (m+n−r) − (m−k) = n. Thus there are （公式略）

paths that start at (0, 0), end at (r, m+n−r), and go through (k, m−k).

Generalizations

Generalized Vandermonde's identity

One can generalize Vandermonde's identity as follows: （公式略）

This identity can be obtained through the algebraic derivation above when more than two polynomials are used, or through a simple double counting argument.

On the one hand, one chooses k₁ elements out of a first set of n₁ elements; then k₂ out of another set, and so on, through p such sets, until a total of m elements have been chosen from the p sets. One therefore chooses m elements out of n₁+… +nₚ in the left-hand side, which is also exactly what is done in the right-hand side.

Chu–Vandermonde identity

The identity generalizes to non-integer arguments. In this case, it is known as the Chu–Vandermonde identity (see Askey 1975, pp. 59–60) and takes the form （公式略）

for general complex-valued s and t and any non-negative integer n. It can be proved along the lines of the algebraic proof above by multiplying the binomial series for (1+x)^(s) and (1+x)^(t) and comparing terms with the binomial series for (1+x)^(s+t).

This identity may be rewritten in terms of the falling Pochhammer symbols as （公式略）

in which form it is clearly recognizable as an umbral variant of the binomial theorem (for more on umbral variants of the binomial theorem, see binomial type). The Chu–Vandermonde identity can also be seen to be a special case of Gauss's hypergeometric theorem, which states that ₂F₁(a,b;c;1)=(Γ (c)Γ (c-a-b))/(Γ (c-a)Γ (c-b))

where ₂F₁ is the hypergeometric function and Γ (n+1)=n! is the gamma function. One regains the Chu–Vandermonde identity by taking a = −n and applying the identity （公式略）

liberally.

The Rothe–Hagen identity is a further generalization of this identity.

The hypergeometric probability distribution

When both sides have been divided by the expression on the left, so that the sum is 1, then the terms of the sum may be interpreted as probabilities. The resulting probability distribution is the hypergeometric distribution. That is the probability distribution of the number of red marbles in r draws without replacement from an urn containing n red and m blue marbles.