一個知道范德蒙恆等式的人，

Vandermonde’s identity

In combinatorics, Vandermonde’s identity, or Vandermonde’s convolution, named after Alexandre-Théophile Vandermonde (1772), states that

{m+n \choose r}=\sum _{{k=0}}^{r}{m \choose k}{n \choose r-k},\qquad m,n,r\in {\mathbb {N}}_{0},

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

{n_{1}+\dots +n_{p} \choose m}=\sum _{k_{1}+\cdots +k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\cdots {n_{p} \choose k_{p}}

是否就能用它來說明

$\sum \limits_{l=0}^{n} {\left( \begin{array}{ccc} n \\ l \end{array} \right)}^2 = {\left( \begin{array}{ccc} 2 n \\ n \end{array} \right)}$ 。

假使他還通熟它的多種證明方法，

Proofs

Algebraic proof

In general, the product of two polynomials with degrees m and n, respectively, is given by

{\biggl (}\sum _{{i=0}}^{m}a_{i}x^{i}{\biggr )}{\biggl (}\sum _{{j=0}}^{n}b_{j}x^{j}{\biggr )}=\sum _{{r=0}}^{{m+n}}{\biggl (}\sum _{{k=0}}^{r}a_{k}b_{{r-k}}{\biggr )}x^{r},

where we use the convention that a_i = 0 for all integers i > m and b_j = 0 for all integers j > n. By the binomial theorem,

(1+x)^{{m+n}}=\sum _{{r=0}}^{{m+n}}{m+n \choose r}x^{r}.

Using the binomial theorem also for the exponents m and n, and then the above formula for the product of polynomials, we obtain

{\begin{aligned}\sum _{{r=0}}^{{m+n}}{m+n \choose r}x^{r}&=(1+x)^{{m+n}}\\&=(1+x)^{m}(1+x)^{n}\\&={\biggl (}\sum _{{i=0}}^{m}{m \choose i}x^{i}{\biggr )}{\biggl (}\sum _{{j=0}}^{n}{n \choose j}x^{j}{\biggr )}\\&=\sum _{{r=0}}^{{m+n}}{\biggl (}\sum _{{k=0}}^{r}{m \choose k}{n \choose r-k}{\biggr )}x^{r},\end{aligned}}

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

{m+n \choose r}.

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:

\sum _{{k=0}}^{r}{m \choose k}{n \choose r-k}.

Geometrical proof

Take a rectangular grid of r x (m+n-r) squares. There are

{\binom {r+(m+n-r)}{r}}={\binom {m+n}{r}}

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 ${\binom {m}{k}}$ 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 ${\binom {n}{r-k}}$ 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

{\binom {m}{k}}{\binom {n}{r-k}}

paths that start at (0,0), end at (r,m+n-r), and go through (k,m-k). This is a subset of all paths that start at (0,0) and end at (r,m+n-r), so sum from k=0 to k=r (as the point (k,m-k) is confined to be within the square) to obtain the total number of paths that start at (0,0) and end at (r,m+n-r).