排列组合恒等式

Abstract

排列组合恒等式（Combinatorial Identities）是关于 $(k n)$ 、 $P (n, r)$ 等计数函数的等式。证明这类恒等式有两种核心方法：双重计数（对同一集合用两种不同方式计数）和双射证明（建立两个集合之间的一一对应）。这些恒等式是二项式系数理论的重要组成部分，在算法分析、概率论和代数中有广泛应用。

定义

双重计数（Double Counting）

双重计数是证明组合恒等式的经典方法：

对同一个有限集合 $S$ ，用两种不同的方式计算 $∣ S ∣$ ，所得结果必然相等。

如果第一种计数方式得到表达式 $A$ ，第二种方式得到表达式 $B$ ，则 $A = B$ 即为要证明的恒等式。

关键在于找到合适的集合 $S$ 和两种自然的计数角度。

双射证明（Bijective Proof）

双射证明通过构造两个集合 $A$ 和 $B$ 之间的双射（一一对应）来证明 $∣ A ∣ = ∣ B ∣$ 。

如果能找到一个双射 $f : A \to B$ ，则 $∣ A ∣ = ∣ B ∣$ 。

双射证明的优势在于不仅证明了数量相等，还揭示了两个组合结构之间的深层联系。

核心性质

编号	恒等式名称	公式	证明方法
1	对称性	$(k n) = (n - k n)$	双射：选 $k$ 个 $\leftrightarrow$ 排除 $n - k$ 个
2	帕斯卡恒等式	$(k n) = (k - 1 n - 1) + (k n - 1)$	双重计数：按是否含特定元素分类
3	全子集求和	$k = 0 \sum n (k n) = 2^{n}$	双重计数： $n$ 元素集合的所有子集
4	范德蒙德卷积	$k = 0 \sum r (k m) (r - k n) = (r m + n)$	双重计数：从两组元素合并后选取
5	曲棍球棒恒等式	$i = r \sum n (r i) = (r + 1 n + 1)$	双重计数 / 数学归纳法
6	交替求和	$k = 0 \sum n (- 1)^{k} (k n) = 0$	二项式定理中令 $x = 1, y = - 1$

关系网络

graph LR
    A["排列组合恒等式"] -->|"证明方法"| B["双重计数"]
    A -->|"证明方法"| C["双射证明"]
    A -->|"证明方法"| D["代数方法"]
    A -->|"核心对象"| E["[[二项式系数]]"]
    A -->|"应用"| F["[[二项式定理]]"]
    B -->|"实例"| G["帕斯卡恒等式"]
    B -->|"实例"| H["范德蒙德卷积"]
    C -->|"实例"| I["对称性"]
    D -->|"实例"| J["交替求和"]
    E -->|"关联"| K["[[组合]]"]
    E -->|"关联"| L["[[排列]]"]

章节扩展

五个经典恒等式详解

恒等式 1：对称性 $(k n) = (n - k n)$

证明（双射法）

构造映射 $f$ ：将每个 $k$ 元子集 $A$ 映射为其补集 $A^{c}$ （ $n - k$ 元子集）。

补集运算是一一对应的（ $A$ 的补集的补集就是 $A$ 本身），因此 $k$ 元子集数等于 $(n - k)$ 元子集数。

恒等式 2：帕斯卡恒等式 $(k n) = (k - 1 n - 1) + (k n - 1)$

证明（双重计数）

从 $n$ 个元素中选 $k$ 个，固定元素 $x$ ：

含 $x$ 的选法：从剩余 $n - 1$ 个中选 $k - 1$ 个，共 $(k - 1 n - 1)$ 种

不含 $x$ 的选法：从剩余 $n - 1$ 个中选 $k$ 个，共 $(k n - 1)$ 种

两者之和即为总数 $(k n)$ 。

恒等式 3：全子集求和 $\sum_{k = 0}^{n} (k n) = 2^{n}$

证明（双重计数）

计算 $n$ 元素集合 $S$ 的所有子集数：

按子集大小分类：大小为 $k$ 的子集有 $(k n)$ 个，求和得 $\sum_{k = 0}^{n} (k n)$

按乘法法则：每个元素有”选入”或”不选入” 2 种选择，共 $2^{n}$ 种

两种方式结果相等。

恒等式 4：范德蒙德卷积 $\sum_{k = 0}^{r} (k m) (r - k n) = (r m + n)$

证明（双重计数）

从 $m$ 个红球和 $n$ 个蓝球中选 $r$ 个球：

按红球个数 $k$ 分类：选 $k$ 个红球（ $(k m)$ ）和 $r - k$ 个蓝球（ $(r - k n)$ ），求和

直接从 $m + n$ 个球中选 $r$ 个： $(r m + n)$

两种方式结果相等。

恒等式 5：曲棍球棒恒等式 $\sum_{i = r}^{n} (r i) = (r + 1 n + 1)$

证明（组合意义）

从 ${1, 2, \dots, n + 1}$ 中选 $r + 1$ 个数 ${a_{1} < a_{2} < \dots < a_{r + 1}}$ ，按最大元素 $a_{r + 1}$ 分类：

若 $a_{r + 1} = i + 1$ （其中 $i \geq r$ ），则前 $r$ 个数从 ${1, \dots, i}$ 中选，有 $(r i)$ 种方式

对 $i$ 从 $r$ 到 $n$ 求和，得 $\sum_{i = r}^{n} (r i)$

这等于直接从 $n + 1$ 个数中选 $r + 1$ 个： $(r + 1 n + 1)$ 。

补充

三种证明方法的比较

方法适用场景优势局限
双重计数 求和式恒等式提供组合直觉，证明优雅需要巧妙的计数角度
双射证明 两集合等势揭示结构对应关系构造双射可能困难
代数方法 含变量的恒等式直接计算，通用性强可能缺乏组合直觉

实际应用中，三种方法往往可以交叉使用，互相验证。

方法	适用场景	优势	局限
双重计数	求和式恒等式	提供组合直觉，证明优雅	需要巧妙的计数角度
双射证明	两集合等势	揭示结构对应关系	构造双射可能困难
代数方法	含变量的恒等式	直接计算，通用性强	可能缺乏组合直觉

代数方法示例

以帕斯卡恒等式为例，用代数方法验证：

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

$= \frac{( n - 1 )! \cdot k}{k ! ( n - k )!} + \frac{( n - 1 )! \cdot ( n - k )}{k ! ( n - k )!}$

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

参见

二项式系数 —— 恒等式的核心对象
组合 —— 组合数的定义与基本性质
排列 —— 排列数与组合数的关系
二项式定理 —— 代数方法证明恒等式的工具
帕斯卡三角形 —— 恒等式的几何可视化

CS Wiki

探索

排列组合恒等式

排列组合恒等式

定义

核心性质

关系网络

章节扩展

五个经典恒等式详解

补充

参见

关系图谱

目录

反向链接