范德蒙恒等式

范德蒙恒等式(英文：Vandermonde's Identity)是一个有关组合数的求和公式。

(\binom{n + m}{k}) = \sum_{i = 0}^{k} (\binom{n}{i}) (\binom{m}{k - i})

证明

组合方法

甲班有 $m$ 个同学，乙班有 $n$ 个同学，从两个班中选出 $k$ 個同學有 $(\binom{n + m}{k})$ 种方法。

从甲班选 $k - i$ 名，从乙班选 $i$ 名有 $(\binom{n}{i}) (\binom{m}{k - i})$ 种方法，考虑所有情况 $i = 0, 1, \dots, k$ ，从两个班中合計 $k$ 选出個同學有 $\sum_{i = 0}^{k} (\binom{n}{i}) (\binom{m}{k - i})$ 种方法。

所以 $(\binom{n + m}{k}) = \sum_{i = 0}^{k} (\binom{n}{i}) (\binom{m}{k - i})$ ^[1]

母函数方法

注意到

(1 + x)^{n} (1 + x)^{m} = (1 + x)^{n + m}

等號左邊化簡成

(1 + x)^{n} (1 + x)^{m} = (\sum_{i = 0}^{n} (\binom{n}{i}) x^{i}) (\sum_{j = 0}^{m} (\binom{m}{j}) x^{j}) = \sum_{k = 0}^{m + n} (\sum_{i = 0}^{k} (\binom{n}{i}) (\binom{m}{k - i})) x^{k}

等號右邊則根據定義

(1 + x)^{n + m} = \sum_{k = 0}^{n + m} (\binom{n + m}{k}) x^{k}

比較 $x^{k}$ 係數，可得

(\binom{n + m}{k}) = \sum_{i = 0}^{k} (\binom{n}{i}) (\binom{m}{k - i})

^[1]

推广

多变量型

$\sum_{k_{i j}} (\binom{n_{1}}{k_{11}, k_{12}, \dots, k_{1 t}}) \dots (\binom{n_{s}}{k_{s 1}, k_{s 2}, \dots, k_{s t}}) = (\binom{n_{1} + n_{2} + \dots + n_{s}}{r_{1}, r_{2}, \dots, r_{t}})$

其中 $(\binom{n}{n_{1}, n_{2}, \dots, n_{m}}) = \frac{n!}{n_{1}! n_{2}! \dots n_{m}!}, k_{1 l} + k_{2 l} + \dots + k_{s l} = r_{l}, l = 1, \dots, t$ ^[2]

展开 $(x_{1} + x_{2} + \dots + x_{t})^{n_{1} + n_{2} + \dots + n_{s}} = (x_{1} + x_{2} + \dots + x_{t})^{n_{1}} \dots (x_{1} + x_{2} + \dots + x_{t})^{n_{s}}$ 可得以上结论。

超几何函数

Template:Main 范德蒙恒等式是超几何函数的一个整数特例。

$_{2} F_{1} (a, b; c; 1) = \sum_{n = 0}^{\infty} \frac{a^{(n)} b^{(n)}}{c^{(n)} n!} = \frac{Γ (c) Γ (c - a - b)}{Γ (c - a) Γ (c - b)}, ℜ (c) > ℜ (a + b)$ ^[3]

$\sum_{i = 0}^{k} (\binom{n}{i}) (\binom{m}{k - i}) = \frac{m!}{k! (m - k)!} \sum_{i = 0}^{\infty} \frac{(- n)^{(i)} (- k)^{(i)}}{(m - k + 1)^{(i)} i!} = \frac{m!}{k! (m - k)!}_{2} F_{1} (- n, - k; m - k + 1; 1)$

$= \frac{m!}{k! (m - k)!} \frac{Γ (m - k + 1) Γ (n + m + 1)}{Γ (n + m - k + 1) Γ (m + 1)} = \frac{(n + m)!}{k! (n + m - k)!} = (\binom{n + m}{k})$

参考资料

Template:Reflist

[model-1] 1.0 ^1.1 Template:Cite journal

[2] Template:Cite journal

[3] Template:Cite book

[1]

[2]

[3]

范德蒙恒等式

目录

证明

组合方法

母函数方法

推广

多变量型

超几何函数

参考资料

导航菜单

范德蒙恒等式

证明

组合方法

母函数方法

推广

多变量型

超几何函数

参考资料

导航菜单

搜索