Appearance
组合恒等式与生成函数
引言
组合恒等式的证明是数学竞赛中的经典题型。从杨辉三角递推到范德蒙德卷积，从二项式定理到卡特兰数，组合恒等式背后有着深刻的结构。生成函数（母函数）作为一种强大的代数工具，能将离散的数列转化为连续的函数，从而用分析或代数手段统一处理计数问题。
前置阅读：二项式定律 | 排列组合 | 求和式的计算方式 | 求积式的计算方式 | 数列与递推方法
一、二项式定理的深化
二项式定理
$$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$
多项式定理（推广）
$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+\cdots+k_m = n} \frac{n!}{k_1!\thinspace{}k_2!\thinspace\cdots\thinspace{}k_m!} \thinspace x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}$$ 其中多项式系数 $\frac{n!}{k_1!\thinspace{}k_2!\thinspace\cdots\thinspace{}k_m!}$ 也是多重集排列数。
二、核心组合恒等式
2.1 杨辉三角递推
帕斯卡恒等式
$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$
组合解释
从 $n$个元素中选$k$个，分为两类：包含某个特定元素$x$的（再从剩余$n-1$个中选$k-1$个，共$\binom{n-1}{k-1}$种）和不包含$x$的（从$n-1$个中选$k$个，共$\binom{n-1}{k}$ 种）。
2.2 行求和与交错和
基本和式
- 行和：$\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$
- 交错和：$\displaystyle \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \quad(n \geq 1)$
- 加权和：$\displaystyle \sum_{k=0}^{n} k\binom{n}{k} = n \cdot 2^{n-1}$
多种证明方法
证明 $\sum_{k=0}^{n} \binom{n}{k} = 2^n$：
- 二项式定理法：令 $x=y=1$，$(1+1)^n = \sum \binom{n}{k}$。
- 组合意义法：左式为 $n$元集合的所有子集个数，每个元素有「选」或「不选」两种选择，共$2^n$ 个。
- 生成函数法：考虑 $(1+x)^n$的生成函数，令$x=1$。
2.3 重要恒等式汇总
必备恒等式
- 对称性：$\binom{n}{k} = \binom{n}{n-k}$
- 吸收恒等式：$k\binom{n}{k} = n\binom{n-1}{k-1}$
- 上指标反转：$\binom{n}{k} = (-1)^k \binom{k-n-1}{k}$（可用于推广到负整数上指标）
- 范德蒙德卷积（见 2.4）
例1：吸收恒等式的应用
计算 $\displaystyle \sum_{k=1}^{n} k^2 \binom{n}{k}$。
- 解析
先用吸收恒等式 $k\binom{n}{k} = n\binom{n-1}{k-1}$， $$\sum_{k=1}^{n} k^2\binom{n}{k} = n\sum_{k=1}^{n} k\binom{n-1}{k-1}$$ 令 $j = k-1$，则 $k = j+1$： $$= n\sum_{j=0}^{n-1} (j+1)\binom{n-1}{j} = n\left(\sum_{j=0}^{n-1} j\binom{n-1}{j} + \sum_{j=0}^{n-1} \binom{n-1}{j}\right)$$ $$= n\left((n-1)2^{n-2} + 2^{n-1}\right) = n(n+1)2^{n-2}$$
:::
2.4 范德蒙德卷积
范德蒙德卷积 (Vandermonde's Identity)
$$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$
组合解释
从 $m$个男生和$n$个女生中选$r$ 人。直接计数：$\binom{m+n}{r}$。按男生人数 $k$分类：选$k$个男生和$r-k$个女生，共$\binom{m}{k}\binom{n}{r-k}$种，对$k$ 求和即得。
例2：范德蒙德卷积的特例
证明：$\displaystyle \sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$。
- 解析
在范德蒙德卷积中取 $m=n$，$r=n$，则： $$\sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k} = \binom{2n}{n}$$ 由 $\binom{n}{n-k} = \binom{n}{k}$ 即得。
:::
三、普通型生成函数 (OGF)
3.1 定义与基本操作
普通型生成函数（Ordinary Generating Function）
对于数列 $\lbrace a_n\rbrace _{n=0}^{\infty}$，其普通型生成函数定义为形式幂级数： $$F(x) = \sum_{n=0}^{\infty} a_n x^n$$
基本操作
| 操作 | 数列 $\lbrace a_n\rbrace $ | 生成函数 |
|---|---|---|
| 加法 | $\lbrace a_n + b_n\rbrace $ | $F(x) + G(x)$ |
| 乘法（卷积） | $\lbrace \sum_{k=0}^{n} a_k b_{n-k}\rbrace $ | $F(x) G(x)$ |
| 移位（右） | $\lbrace 0, a_0, a_1, \ldots\rbrace $ | $x F(x)$ |
| 求导 | $\lbrace (n+1)a_{n+1}\rbrace $ | $F'(x)$ |
| 标量乘 $n$ | $\lbrace n a_n\rbrace $ | $x F'(x)$ |
3.2 常见数列的 OGF
常见 OGF 速查表
$$\begin{aligned} \text{常数列 } a_n = 1 &: \quad \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \quad (|x| < 1) \newline a_n = n &: \quad \sum_{n=0}^{\infty} n x^n = \frac{x}{(1-x)^2} \newline \binom{m}{n} \text{（固定上指标）} &: \quad (1+x)^m = \sum_{n=0}^{m} \binom{m}{n} x^n \newline \binom{n+m-1}{n} \text{（可重组合）} &: \quad \frac{1}{(1-x)^m} = \sum_{n=0}^{\infty} \binom{n+m-1}{n} x^n \end{aligned}$$
例3：利用 OGF 求数列和
求 $\displaystyle \sum_{n=0}^{\infty} \frac{n}{2^n}$。
- 解析
已知 $\sum_{n=0}^{\infty} nx^n = \frac{x}{(1-x)^2}$，代入 $x = 1/2$： $$\sum_{n=0}^{\infty} \frac{n}{2^n} = \frac{1/2}{(1-1/2)^2} = \frac{1/2}{1/4} = 2$$
:::
四、指数型生成函数 (EGF)
指数型生成函数（Exponential Generating Function）
对于数列 $\lbrace a_n\rbrace _{n=0}^{\infty}$，其指数型生成函数定义为： $$F(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$$
为什么需要 EGF？
当计数对象带有标号（labeled）时（如标号图、排列等），EGF 的乘法自然对应标号对象的组合：「从 $n$个标号元素中选$k$个给第一个结构，剩余$n-k$ 个给第二个结构」的组合数恰好对应 EGF 系数的二项式卷积。
常见数列的 EGF
$$\begin{aligned} a_n = 1 &: \quad \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x \newline a_n = n! \quad \text{（排列数）} &: \quad \sum_{n=0}^{\infty} n! \cdot \frac{x^n}{n!} = \frac{1}{1-x} \newline a_n = D_n \quad \text{（错位排列数）} &: \quad \sum_{n=0}^{\infty} D_n \frac{x^n}{n!} = \frac{e^{-x}}{1-x} \end{aligned}$$
例4：EGF 证明恒等式
证明：$\displaystyle \sum_{k=0}^{n} \binom{n}{k} D_{n-k} = n!$。（其中 $D_0 = 1$）
- 解析
考虑排列的 EGF：全排列的 EGF 为 $\frac{1}{1-x}$。将一个排列分解为若干个大小为 $1$ 的循环（即不动点）和错位排列的组合。 不动点的 EGF 为 $e^x$，错位排列的 EGF 为 $\frac{e^{-x}}{1-x}$。二者的乘积 $e^x \cdot \frac{e^{-x}}{1-x} = \frac{1}{1-x}$，恰好等于全排列的 EGF。提取 $x^n/n!$ 的系数即得恒等式。
:::
五、卡特兰数 (Catalan Numbers)
卡特兰数定义
卡特兰数 $C_n$ 定义为： $$C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}$$ 前几项：$C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42$
卡特兰数的常见组合解释
- $n$ 对括号的合法匹配方案数
- $n+1$ 个节点的二叉树形态数
- 凸 $n+2$ 边形的三角剖分数
- 从 $(0,0)$到$(n,n)$ 不越过对角线的格路数
- $n$ 个元素的出栈序列数
生成函数
卡特兰数的生成函数 $C(x) = \sum_{n=0}^{\infty} C_n x^n$ 满足： $$C(x) = 1 + x\thinspace{}C(x)^2$$ 解得 $C(x) = \dfrac{1 - \sqrt{1-4x}}{2x}$，由此展开可得通项公式。
例5：卡特兰数递推证明
用生成函数证明卡特兰数满足递推 $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$（$C_0 = 1$）。
- 证明
由 $C(x) = 1 + x C(x)^2$： $$C(x) = 1 + x \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} C_k C_{n-k}\right) x^n$$ 比较 $x^n$（$n \geq 1$）的系数：$C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$。这正是递推式的生成函数证明。
:::
六、三道经典例题的三种证法
例6：证明 $\displaystyle \sum_{k=0}^{n} k\binom{n}{k} = n \cdot 2^{n-1}$
- 证法一（代数法 / 吸收恒等式）
$$k\binom{n}{k} = n\binom{n-1}{k-1}$$ $$\sum_{k=0}^{n} k\binom{n}{k} = n\sum_{k=1}^{n} \binom{n-1}{k-1} = n\sum_{j=0}^{n-1} \binom{n-1}{j} = n \cdot 2^{n-1}$$
- 证法二（组合意义法）
左式：从 $n$ 人中选出一个委员会（任意大小），并从中指定一位主席。 等价做法：先从 $n$ 人中选主席（$n$种），再从剩余$n-1$人中选委员会其余成员（每人选或不选，共$2^{n-1}$种）。故为$n \cdot 2^{n-1}$。
- 证法三（生成函数法 / 母函数法）
令 $f(x) = (1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$。求导得： $$f'(x) = n(1+x)^{n-1} = \sum_{k=1}^{n} k\binom{n}{k} x^{k-1}$$ 令 $x = 1$：$n \cdot 2^{n-1} = \sum_{k=1}^{n} k\binom{n}{k}$，得证。
:::
例7：利用生成函数求数列通项
已知数列 $\lbrace a_n\rbrace $满足$a_0 = 1$，$a_{n+1} = 2a_n + 1$（$n \geq 0$），求 $a_n$。
- 解析
设 $F(x) = \sum a_n x^n$。由递推： $$\sum_{n=0}^{\infty} a_{n+1} x^n = 2\sum_{n=0}^{\infty} a_n x^n + \sum_{n=0}^{\infty} x^n$$ 即 $\frac{F(x)-a_0}{x} = 2F(x) + \frac{1}{1-x}$。 解得 $F(x) = \frac{1}{1-2x} + \frac{x}{(1-2x)(1-x)} = \frac{2}{1-2x} - \frac{1}{1-x}$ 展开得 $a_n = 2 \cdot 2^n - 1 = 2^{n+1} - 1$。
:::
七、生成函数技巧进阶
7.1 部分分式分解法
技巧
当生成函数为有理函数 $\frac{P(x)}{Q(x)}$时，可将其分解为$\sum \frac{A_i}{(1-r_i x)^{m_i}}$之和，利用$(1-rx)^{-m}$的展开式$\sum \binom{n+m-1}{n} r^n x^n$ 提取系数。
7.2 Snake Oil Method
Herbert Wilf 的 Snake Oil 方法
对于形如 $\sum_k \binom{n}{k} a_k$的和式，可引入自由变量$n$，构造关于 $n$ 的生成函数，交换求和次序，化简后再提取系数。
7.3 系数提取算子 $[x^n]$
系数算子
$[x^n] F(x)$表示生成函数$F(x)$中$x^n$ 的系数。常用性质：
- $[x^n] x^k F(x) = [x^{n-k}] F(x)$
- $[x^n] F'(x) = (n+1) [x^{n+1}] F(x)$
- $[x^n] F(x) G(x) = \sum_{k=0}^{n} [x^k]F(x) \cdot [x^{n-k}] G(x)$
八、Lagrange 反演公式
Lagrange 反演
设 $F(x)$满足$F(x) = x \phi(F(x))$，其中 $\phi(0) \ne 0$。则对任意 $n \ge 1$： $$[x^n] F(x) = \frac{1}{n} [t^{n-1}] \phi(t)^n$$ 更一般地，对任意函数 $H$： $$[x^n] H(F(x)) = \frac{1}{n} [t^{n-1}] H'(t) \phi(t)^n$$
用途
Lagrange 反演是处理「隐式递推」的利器。当数列通过 $a_n = f(a_0, \ldots, a_{n-1})$ 隐式给出（如 Catalan、Motzkin、Schroder 数等树状结构计数），Lagrange 反演常给出闭式系数公式。
例8：Catalan 数的 Lagrange 反演推导
Catalan 数的生成函数 $C(x) = 1 + x C(x)^2$，即 $C(x) - 1 = x C(x)^2$。令 $F(x) = C(x) - 1$，则 $F = x(1+F)^2$，即 $\phi(t) = (1+t)^2$。 由 Lagrange 反演： $$[x^n] F(x) = \frac{1}{n} [t^{n-1}] (1+t)^{2n} = \frac{1}{n} \binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n}$$ 此即 $C_n$（$n \ge 1$），与已知结果一致。
例9：Motzkin 数
Motzkin 数 $M_n$满足$M(x) = 1 + x M(x) + x^2 M(x)^2$，对应路径不越过 $x$轴且每步$\nearrow, \to, \searrow$的方案数。Lagrange 反演可给出$M_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{1}{k+1} \binom{n}{2k} \binom{2k}{k}$。
九、指数公式（标号结构计数）
指数公式（Exponential Formula）
设 $\mathcal{A}$为「连通」标号组合结构类，其 EGF 为$A(x) = \sum_{n} a_n \frac{x^n}{n!}$。由 $\mathcal{A}$-型连通分量构成的「集合」结构 $\mathcal{S} = \text{SET}(\mathcal{A})$ 的 EGF 为 $$S(x) = \exp(A(x)) = \sum_{k=0}^{\infty} \frac{A(x)^k}{k!}$$ 系数含义：$n$元标号集分解为若干无序连通分量（每分量属$\mathcal{A}$）的方案数 $s_n$满足$S(x) = \sum_n s_n \frac{x^n}{n!}$。
重要推论
- 置换 $\to$圈分解：置换是「有向圈的集合」，圈结构 EGF 为$A(x) = \log\frac{1}{1-x}$，故置换的 EGF $S(x) = \exp(\log\frac{1}{1-x}) = \frac{1}{1-x}$，对应 $n! = s_n$。
- 集合划分 $\to$集合：集合划分为非空子集，单分量 EGF 为$A(x) = e^x - 1$，集合划分的 EGF 为 $S(x) = \exp(e^x - 1)$，即 Bell 数 $B_n$ 的 EGF。
- 图 $\to$连通图：所有标号图的 EGF$G(x) = \sum 2^{\binom{n}{2}} \frac{x^n}{n!}$，连通图 EGF 为 $C(x) = \log G(x)$。
例10：Bell 数的 EGF
Bell 数 $B_n$是$n$ 元集合的划分数。由指数公式，$B(x) = \sum_n B_n \frac{x^n}{n!} = \exp(e^x - 1)$。求导得 $B'(x) = e^x B(x)$，比较系数有 $B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$（Bell 递推）。
例11：连通图计数
$n$个顶点的标号图总数$G_n = 2^{\binom{n}{2}}$，对应 EGF $G(x) = \sum_n 2^{\binom{n}{2}} \frac{x^n}{n!}$。连通图 EGF $C(x) = \log G(x)$，故连通图数 $c_n = n! [x^n] \log G(x)$。
十、多元生成函数与对角线法
多元 OGF
数列 $\lbrace a_{n_1, \ldots, n_k}\rbrace $的$k$元 OGF 为$F(x_1, \ldots, x_k) = \sum_{n_1, \ldots, n_k \ge 0} a_{n_1, \ldots, n_k} x_1^{n_1} \cdots x_k^{n_k}$。
对角线
对二元 GF $F(x, y) = \sum_{m, n \ge 0} a_{m, n} x^m y^n$，其对角线为 $\sum_{n \ge 0} a_{n, n} t^n$。对角线在组合渐近分析（如 Delannoy 数、格点路径）中起核心作用。
例12：Delannoy 数
Delannoy 数 $D(m, n)$是从$(0,0)$到$(m,n)$允许$\to, \uparrow, \nearrow$ 三种步的路径数。二元 OGF 为 $$D(x, y) = \frac{1}{1 - x - y - xy}$$ 对角线 $D_n = D(n, n)$的 OGF 为$\frac{1}{1 - 6t + t^2}^{1/2}$ 的展开系数（中心 Delannoy 数）。
十一、Dirichlet 生成函数
Dirichlet 生成函数（DGF）
数列 $\lbrace a_n\rbrace _{n=1}^{\infty}$ 的 DGF 为 $$D(s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$$ Dirichlet 卷积 $a * b$ 对应 DGF 的乘积：$D_{a*b}(s) = D_a(s) D_b(s)$。
重要例子
- $a_n = 1$：$D(s) = \zeta(s)$（Riemann zeta 函数）
- $a_n = \mu(n)$（Möbius）：$D(s) = 1/\zeta(s)$
- $a_n = \varphi(n)$：$D(s) = \zeta(s-1)/\zeta(s)$
- $a_n = d(n)$（约数个数）：$D(s) = \zeta(s)^2$
与 OGF 的对比
- OGF 对应「位置卷积」（序列错位相乘求和）
- EGF 对应「标号卷积」（二项式系数）
- DGF 对应「Dirichlet 卷积」（按因子分解） 三种 GF 各自适配不同组合结构。详见 数论函数与欧拉定理、素数分布与解析数论初步。
十二、组合恒等式的「组合证明」哲学
Aigner–Ziegler《Proofs from THE BOOK》精神
组合证明的至高境界是「双射证明」：用一一映射直接说明等式两边的对象数相同，无需代数变形。
例13：$\sum_k \binom{n}{k}^2 = \binom{2n}{n}$ 的双射证明
左边：从 $n$男$n$女中选$n$人，按男生数$k$分类，方案$\binom{n}{k}^2$。右边：直接选 $\binom{2n}{n}$。双射显然。
例14：$k\binom{n}{k} = n\binom{n-1}{k-1}$ 的双射证明
左边：选 $k$ 人委员会并选主席。右边：先选主席（$n$种），再从剩余$n-1$人中选$k-1$ 名委员。两种方式计数同一对象。
三大证明范式
- 代数证明：用二项式定理、求导、积分等代数操作。
- 组合证明：构造双射或双重计数。
- 生成函数证明：将等式转化为 GF 系数比较。 三者互为补充，竞赛中综合运用。