第7章生成函数 (Generating Functions)

一、导读

7.1 本章学习目标

在本章结束时，你将能够：

理解生成函数的基本概念和形式幂级数表示
运用生成函数求解递推关系
掌握常见序列的生成函数：斐波那契、卡特兰等
使用部分分式分解提取系数
应用指数生成函数处理排列问题
理解卷积运算与生成函数的关系
掌握生成函数的代数操作：加法、乘法、复合
了解狄利克雷生成函数在数论中的应用
掌握多变量生成函数的基本概念
理解生成函数与渐近分析的联系

7.2 为什么本章如此重要

生成函数是组合数学中最强大的工具之一。它将离散序列转化为连续的代数对象，使得我们可以用微积分、代数等方法来研究组合问题。

赫伯特·威尔夫（Herbert Wilf）称生成函数为"概率论中的矩母函数在组合数学中的对应物"。生成函数的威力在于：

统一框架：将各种计数问题纳入统一的代数框架

自动计算：通过代数操作自动得到组合恒等式

渐近分析：通过复分析提取系数的渐近行为

算法设计：动态规划、多项式乘法等算法的理论基础

概率分析：矩母函数、特征函数都是生成函数的变体

结构洞察：生成函数的奇点位置决定了序列的增长速率

对于程序员而言，生成函数不仅是理论工具，更是解决实际问题的利器。从算法分析到密码学，从数据结构到机器学习，生成函数都有广泛应用。例如，在分析快速排序的平均情况时，生成函数可以帮助我们将复杂的递推关系转化为可解的方程；在设计动态规划算法时，生成函数的卷积对应于状态转移的组合。

《具体数学》将生成函数放在后期章节，是因为它综合运用了前面所学的求和、二项式系数、特殊数等工具。生成函数是将离散数学与连续数学、有限与无限联系起来的桥梁。

7.3 核心问题引导

什么是生成函数？它与普通函数有何区别？

如何将递推关系转化为生成函数的方程？

部分分式分解如何帮助提取系数？

普通生成函数和指数生成函数有什么区别？

生成函数的卷积对应什么组合操作？

如何用生成函数解决卡特兰数的计数问题？

生成函数与傅里叶变换有何联系？

如何处理非线性递推关系的生成函数？

生成函数的收敛半径对组合意义有何影响？

多变量生成函数如何处理多维计数问题？

二、核心概念详解

7.1 生成函数的定义

普通生成函数

定义：对于序列 a₀, a₁, a₂, ...，其普通生成函数（Ordinary Generating Function, OGF）定义为形式幂级数：

$$A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \cdots$$

关键点：生成函数是"形式"幂级数，我们关心的是系数 aₙ，而不一定关心级数是否收敛。x 只是一个占位符，用于标记序列中元素的位置。这种形式化的观点使我们能够避免收敛性的复杂讨论，专注于代数操作。

示例：

常数序列 1, 1, 1, ... 的生成函数：$\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$（当 |x| < 1 时收敛）
序列 1, 2, 3, ... 的生成函数：$\sum_{n=0}^{\infty} (n+1)x^n = \frac{1}{(1-x)^2}$
序列 1, 0, 1, 0, 1, ... 的生成函数：$\sum_{n=0}^{\infty} x^{2n} = \frac{1}{1-x^2}$
二项式系数序列 $\binom{n}{k}$（固定 k）的生成函数：$\sum_{n=k}^{\infty} \binom{n}{k} x^n = \frac{x^k}{(1-x)^{k+1}}$

直觉解释：生成函数可以看作是一个"魔法盒子"，将整个序列编码为一个单一的代数对象。通过对这个对象进行操作，我们可以同时处理序列的所有元素。这种视角转换是生成函数力量的源泉。

指数生成函数

定义：对于序列 a₀, a₁, a₂, ...，其指数生成函数（Exponential Generating Function, EGF）定义为：

$$\hat{A}(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} = a_0 + a_1 x + a_2 \frac{x^2}{2!} + \cdots$$

指数生成函数在处理排列问题时特别有用，因为 n! 自然地出现在排列计数中。

示例：

序列 1, 1, 1, ... 的EGF：$\sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x$
序列 1!, 2!, 3!, ... 的EGF：$\sum_{n=0}^{\infty} n! \frac{x^n}{n!} = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$
序列 $2^n$ 的EGF：$\sum_{n=0}^{\infty} 2^n \frac{x^n}{n!} = e^{2x}$

OGF与EGF的选择：

当组合对象是"无标签"的（如整数划分、组合），使用OGF
当组合对象是"有标签"的（如排列、带标号图），使用EGF

狄利克雷生成函数

定义：对于数论函数 a(n)，其狄利克雷生成函数定义为：

$$D(s) = \sum_{n=1}^{\infty} \frac{a(n)}{n^s}$$

这在解析数论中有重要应用，如黎曼ζ函数就是 a(n)=1 的狄利克雷生成函数。

性质：如果 c(n) = Σ_{d|n} a(d)b(n/d)（狄利克雷卷积），则 C(s) = A(s)B(s)。这与普通生成函数中卷积对应乘法的性质类似。

示例：

黎曼ζ函数：$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}$
莫比乌斯函数的狄利克雷生成函数：$\sum_{n=1}^{\infty} \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}$
除数函数 d(n) 的狄利克雷生成函数：$\sum_{n=1}^{\infty} \frac{d(n)}{n^s} = \zeta(s)^2$

7.2 基本操作的组合意义

加法

如果 A(x) 是序列 {aₙ} 的生成函数，B(x) 是序列 {bₙ} 的生成函数，则：

$$A(x) + B(x) = \sum_{n=0}^{\infty} (a_n + b_n) x^n$$

组合意义：两个不相交集合的计数的和。例如，如果 aₙ 表示用红色方块铺满 2×n 矩形的方法数，bₙ 表示用蓝色方块的方法数，则 aₙ+bₙ 表示用红色或蓝色方块的方法数。

更深层的理解：加法对应于组合类的"不交并"操作。如果我们有两类互斥的对象，它们的生成函数相加就得到了合并后的类的生成函数。

乘法（卷积）

$$A(x)B(x) = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} a_k b_{n-k}\right) x^n$$

系数 $c_n = \sum_{k=0}^{n} a_k b_{n-k}$ 称为序列 {aₙ} 和 {bₙ} 的卷积。

组合意义：将一个大小为 n 的对象分解为两部分（大小分别为 k 和 n-k），分别用 aₖ 和 bₙ₋ₖ 种方式构造，然后对所有可能的 k 求和。

示例：设 A(x) = B(x) = $\frac{1}{1-x} = 1+x+x^2+\cdots$，则：

$$A(x)B(x) = \frac{1}{(1-x)^2} = \sum_{n=0}^{\infty} (n+1)x^n$$

系数 n+1 正是将 n 分为两个非负整数之和的方法数（0+n, 1+(n-1), ..., n+0）。

另一个示例：卡特兰数的递推关系 Cₙ = Σᵢ CᵢCₙ₋₁₋ᵢ 本质上是一个卷积，对应于生成函数方程 C(x) = 1 + xC(x)²。这里的 x 因子对应于根节点，而卷积对应于左右子树的组合。

卷积的直观理解：想象你有两种类型的积木，类型A有 aₖ 种方式搭建高度为 k 的结构，类型B有 bₘ 种方式搭建高度为 m 的结构。如果你想搭建总高度为 n 的结构，可以将高度分配给两种类型，所有分配方式的总和就是卷积。

移位

$$x^k A(x) = \sum_{n=k}^{\infty} a_{n-k} x^n$$

组合意义：将序列向右平移 k 位，前面补零。这在处理带初始条件的递推关系时非常有用。

应用示例：在斐波那契数列的生成函数推导中，我们需要处理 F(x) - F₀ - F₁x 这样的表达式，这本质上是将序列向左移位。

微分

$$A'(x) = \sum_{n=1}^{\infty} n a_n x^{n-1} = \sum_{n=0}^{\infty} (n+1)a_{n+1} x^n$$

组合意义：加权序列，每个元素乘以其下标。这在计算期望值和方差时有用。

示例：如果 A(x) = $\frac{1}{1-x}$，则 $A'(x) = \frac{1}{(1-x)^2} = \sum_{n=0}^{\infty} (n+1)x^n$。

高阶微分：$A^{(k)}(x) = \sum_{n=k}^{\infty} n(n-1)\cdots(n-k+1) a_n x^{n-k}$。这可以用来提取形如 $\binom{n}{k} a_n$ 的系数。

组合应用：微分操作对应于在组合对象中"标记"一个元素。例如，如果 A(x) 计数某种结构，则 xA'(x) 计数带有单个标记元素的结构。

积分

$$\int_0^x A(t) dt = \sum_{n=0}^{\infty} \frac{a_n}{n+1} x^{n+1}$$

组合意义：每个元素除以其下标加1。

应用：积分可以用于"去加权"，即消除微分引入的下标因子。

复合

$$A(B(x)) = \sum_{n=0}^{\infty} a_n (B(x))^n$$

组合意义：嵌套结构。例如，如果 B(x) 表示某种基本结构的生成函数，则 A(B(x)) 表示由这些基本结构组成的复合结构的生成函数。

示例：如果 B(x) 是非空集合的EGF（即 eˣ-1），则 exp(B(x)) = exp(eˣ-1) 是集合划分的EGF（Bell数）。

复合的条件：通常要求 B(0) = 0，以确保复合后的级数仍然是形式幂级数。

Hadamard积

定义：两个生成函数的Hadamard积定义为系数逐项相乘：

$$A(x) \odot B(x) = \sum_{n=0}^{\infty} a_n b_n x^n$$

组合意义：同时满足两种约束的对象计数。

计算方法：Hadamard积没有简单的闭式表达，但可以通过围道积分计算：

$$x^n = \frac{1}{2\pi i} \oint \frac{A(z)B(x/z)}{z} dz$$

7.3 求解递推关系

生成函数最强大的应用之一是求解递推关系。以下是标准步骤：

步骤1：设 A(x) = Σ aₙxⁿ 是待求序列的生成函数。

步骤2：将递推关系两边乘以 xⁿ 并对 n 求和。

步骤3：用 A(x) 表示各个求和项。

步骤4：解出 A(x) 的闭合形式。

步骤5：从 A(x) 中提取系数 aₙ。

示例1：斐波那契数列

斐波那契数列满足：F₀=0, F₁=1, Fₙ = Fₙ₋₁ + Fₙ₋₂（n ≥ 2）。

设 $F(x) = \sum_{n=0}^{\infty} F_n x^n$。

由递推关系：

$$\sum_{n=2}^{\infty} F_n x^n = \sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n$$

左边 = F(x) - F₀ - F₁x = F(x) - x。

右边第一项 = $x\sum_{n=2}^{\infty} F_{n-1} x^{n-1} = x(F(x) - F_0) = xF(x)$。

右边第二项 = $x^2\sum_{n=2}^{\infty} F_{n-2} x^{n-2} = x^2 F(x)$。

所以：F(x) - x = xF(x) + x²F(x)。

解得：$F(x) = \frac{x}{1-x-x^2}$。

为了提取系数，进行部分分式分解。特征方程 1-x-x² = 0 的根为 $x = \frac{-1\pm\sqrt{5}}{2}$。

令 $\alpha = \frac{1+\sqrt{5}}{2} = \phi$，$\beta = \frac{1-\sqrt{5}}{2} = \psi$。注意 $1-x-x^2 = -(x-\frac{1}{\alpha})(x-\frac{1}{\beta}) \cdot \alpha\beta$。

更直接地，我们可以写：

$$F(x) = \frac{x}{1-x-x^2} = \frac{1}{\sqrt{5}}\left(\frac{1}{1-\alpha x} - \frac{1}{1-\beta x}\right)$$

展开：

$$F(x) = \frac{1}{\sqrt{5}}\left(\sum_{n=0}^{\infty} \alpha^n x^n - \sum_{n=0}^{\infty} \beta^n x^n\right) = \sum_{n=0}^{\infty} \frac{\alpha^n - \beta^n}{\sqrt{5}} x^n$$

因此 $F_n = \frac{\alpha^n - \beta^n}{\sqrt{5}}$，这正是比内公式！

深入分析：注意 β = -1/φ ≈ -0.618，其绝对值小于1，所以当 n 很大时，βⁿ 趋近于0。因此 Fₙ ≈ φⁿ/√5，这解释了斐波那契数列的指数增长特性。

示例2：线性递推

考虑递推关系：aₙ = 3aₙ₋₁ - 2aₙ₋₂，a₀=1, a₁=2。

设 $A(x) = \sum_{n=0}^{\infty} a_n x^n$。

$$\sum_{n=2}^{\infty} a_n x^n = 3\sum_{n=2}^{\infty} a_{n-1} x^n - 2\sum_{n=2}^{\infty} a_{n-2} x^n$$

左边 = A(x) - a₀ - a₁x = A(x) - 1 - 2x。

右边 = 3x(A(x) - a₀) - 2x²A(x) = 3x(A(x) - 1) - 2x²A(x)。

所以：A(x) - 1 - 2x = 3xA(x) - 3x - 2x²A(x)。

整理：A(x)(1 - 3x + 2x²) = 1 - x。

$$A(x) = \frac{1-x}{1-3x+2x^2} = \frac{1-x}{(1-x)(1-2x)} = \frac{1}{1-2x} = \sum_{n=0}^{\infty} 2^n x^n$$

因此 aₙ = 2ⁿ。验证：a₀=1=2⁰ ✓，a₁=2=2¹ ✓，a₂=3×2-2×1=4=2² ✓。

一般理论：对于常系数线性递推 aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ，生成函数总是有理函数 P(x)/Q(x)，其中 Q(x) = 1 - c₁x - c₂x² - ... - cₖxᵏ。Q(x) 的根的倒数就是特征方程的根。

示例3：非齐次递推

考虑 aₙ = 2aₙ₋₁ + n，a₀ = 1。

设 $A(x) = \sum_{n=0}^{\infty} a_n x^n$。

$$\sum_{n=1}^{\infty} a_n x^n = 2\sum_{n=1}^{\infty} a_{n-1} x^n + \sum_{n=1}^{\infty} n x^n$$

左边 = A(x) - 1。

右边第一项 = 2xA(x)。

右边第二项 = $x\frac{d}{dx}\sum_{n=0}^{\infty} x^n = x\frac{d}{dx}\frac{1}{1-x} = \frac{x}{(1-x)^2}$。

所以：A(x) - 1 = 2xA(x) + $\frac{x}{(1-x)^2}$。

解得：$A(x) = \frac{1}{1-2x} + \frac{x}{(1-2x)(1-x)^2}$。

通过部分分式分解，可以得到 aₙ 的闭合形式。

7.4 卡特兰数的生成函数

卡特兰数满足递推关系：$C_0 = 1$，$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$（n ≥ 1）。

设 $C(x) = \sum_{n=0}^{\infty} C_n x^n$。

注意到递推关系的右边是卷积形式：

$$\sum_{n=1}^{\infty} C_n x^n = x \sum_{n=1}^{\infty} \left(\sum_{i=0}^{n-1} C_i C_{n-1-i}\right) x^{n-1} = x C(x)^2$$

左边 = C(x) - C₀ = C(x) - 1。

所以：C(x) - 1 = xC(x)²，即 xC(x)² - C(x) + 1 = 0。

解二次方程：

$$C(x) = \frac{1 \pm \sqrt{1-4x}}{2x}$$

由于 C(0) = 1，取负号（因为取正号时在 x=0 处发散）：

$$C(x) = \frac{1 - \sqrt{1-4x}}{2x}$$

用二项式定理展开 $\sqrt{1-4x} = (1-4x)^{1/2}$：

$$(1-4x)^{1/2} = \sum_{n=0}^{\infty} \binom{1/2}{n} (-4x)^n$$

其中 $\binom{1/2}{n} = \frac{(1/2)(-1/2)(-3/2)\cdots(1/2-n+1)}{n!}$。

经过化简，可得：

$$[x^n]C(x) = \frac{1}{n+1}\binom{2n}{n} = C_n$$

这正是卡特兰数的闭合形式！

卡特兰数的多种解释：

n 对括号的合法匹配方式数

n+1 个叶子节点的满二叉树数量

凸 n+2 边形的三角剖分数

不超过对角线的格路路径数

栈的合法输出序列数

所有这些计数问题都共享相同的递归结构，因此都由卡特兰数计数。

7.5 部分分式分解

部分分式分解是从有理生成函数中提取系数的关键技术。

基本原理：如果 $A(x) = \frac{P(x)}{Q(x)}$ 是有理函数，且 Q(x) 可以分解为线性因子的乘积，则 A(x) 可以写成简单分式的和。

示例：设 $A(x) = \frac{1}{(1-x)(1-2x)}$。

设 $\frac{1}{(1-x)(1-2x)} = \frac{a}{1-x} + \frac{b}{1-2x}$。

通分：$1 = a(1-2x) + b(1-x)$。

令 x = 1：1 = a(-1)，所以 a = -1。

令 x = 1/2：1 = b(1/2)，所以 b = 2。

因此：

$$A(x) = \frac{-1}{1-x} + \frac{2}{1-2x} = -\sum_{n=0}^{\infty} x^n + 2\sum_{n=0}^{\infty} (2x)^n = \sum_{n=0}^{\infty} (2^{n+1} - 1) x^n$$

所以 aₙ = 2ⁿ⁺¹ - 1。

一般方法：

对分母进行因式分解

设定部分分式的形式

通分后比较系数或代入特殊值求解

重根情况：如果 Q(x) 有重根，如 $(1-x)^2$，则部分分式中包含 $\frac{a}{1-x} + \frac{b}{(1-x)^2}$ 等形式。

示例：$\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty} (n+1)x^n$。

复根情况：如果 Q(x) 有复根，部分分式可能涉及复数，但最终系数一定是实数（如果原函数系数为实数）。

7.6 指数生成函数的应用

指数生成函数在处理带标签的对象（如排列）时特别有用。

示例1：排列数 n! 的EGF是：

$$\sum_{n=0}^{\infty} n! \frac{x^n}{n!} = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$$

示例2：集合划分的EGF。

设 Bₙ 是 Bell 数（n 个元素的集合划分总数）。其EGF为：

$$\hat{B}(x) = e^{e^x - 1}$$

这是因为一个集合划分可以看作是将集合划分为若干个非空子集，而每个非空子集的EGF是 eˣ - 1，任意多个这样的子集的EGF是 exp(eˣ - 1)。

示例3：错排数的EGF。

设 Dₙ 是错排数。其EGF为：

$$\hat{D}(x) = \frac{e^{-x}}{1-x}$$

推导：任何排列可以唯一分解为一个错排和一个固定点的集合。排列的EGF是 $\frac{1}{1-x}$，固定点集合的EGF是 eˣ，错排的EGF是 $\hat{D}(x)$。由指数公式，$\frac{1}{1-x} = e^x \hat{D}(x)$，所以 $\hat{D}(x) = \frac{e^{-x}}{1-x}$。

指数公式：如果 $\hat{A}(x)$ 是某种"连通"结构的EGF，则 $\exp(\hat{A}(x))$ 是由这些连通结构组成的任意集合的EGF。这是组合结构理论中的核心结果。

7.7 生成函数的其他类型

狄利克雷生成函数

对于数论函数 a(n)，狄利克雷生成函数定义为：

$$D(s) = \sum_{n=1}^{\infty} \frac{a(n)}{n^s}$$

示例：黎曼ζ函数是 a(n)=1 的狄利克雷生成函数：

$$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}$$

性质：如果 c(n) = Σ_{d|n} a(d)b(n/d)（狄利克雷卷积），则 C(s) = A(s)B(s)。

朗伯级数

朗伯级数（Lambert Series）定义为：

$$L(x) = \sum_{n=1}^{\infty} a_n \frac{x^n}{1-x^n}$$

这在数论中有应用，如除数函数的生成函数。

示例：除数函数 d(n) 的朗伯级数为：

$$\sum_{n=1}^{\infty} d(n) x^n = \sum_{n=1}^{\infty} \frac{x^n}{1-x^n}$$

7.8 多变量生成函数

定义：对于双索引序列 a_{m,n}，二元生成函数定义为：

$$A(x,y) = \sum_{m=0}^{\infty} \sum_{n=0}^{\infty} a_{m,n} x^m y^n$$

应用：多变量生成函数可以处理更复杂的计数问题，如同时跟踪多个参数。

示例：二项式系数的二元生成函数：

$$\sum_{m=0}^{\infty} \sum_{n=0}^{\infty} \binom{m+n}{m} x^m y^n = \frac{1}{1-x-y}$$

提取对角线：有时我们只关心 a_{n,n}，这可以通过围道积分或其他技术从二元生成函数中提取。

三、程序员的视角

7.1 在算法中的应用

多项式乘法

生成函数的乘法对应于序列的卷积，可以用FFT（快速傅里叶变换）在 O(n log n) 时间内计算。

应用：大整数乘法、信号处理、模式匹配。

实现细节：在实际编程中，可以使用现成的FFT库（如FFTW）来实现高效的多项式乘法。对于整数系数，需要注意数值精度问题。

动态规划优化

许多DP问题的转移方程本质上是生成函数的乘法。通过生成函数，可以将某些O(n²)的DP优化为O(n log n)。

示例：背包问题中，如果物品重量为 wᵢ，价值为 vᵢ，则总价值的生成函数是各物品生成函数的乘积。

更深入的例子：考虑计算将整数 n 表示为正整数之和的方法数（整数划分）。朴素DP需要 O(n²) 时间，但使用生成函数和FFT可以加速。

概率生成函数

在随机算法分析中，概率生成函数 G(z) = E[z^X] 用于计算期望和方差。

性质：

E[X] = G'(1)
Var(X) = G''(1) + G'(1) - [G'(1)]²

应用：分析随机快速排序的比较次数、哈希表的冲突数等。

形式幂级数算法

在计算机代数系统中，形式幂级数的操作（加法、乘法、求逆、复合等）有专门的算法。这些算法的复杂度通常为 O(n log n) 或 O(n log² n)。

应用：符号计算、组合枚举、算法分析。

7.2 常见陷阱

陷阱1：收敛性问题

形式幂级数不关心收敛性，但在数值计算时需要注意。如果需要在特定点求值，必须确保该点在收敛半径内。

解决方法：在进行数值计算前，先分析生成函数的奇点位置，确定收敛半径。

陷阱2：系数提取错误

部分分式分解后，确保正确识别每个简单分式的系数。特别注意重根情况和复根情况。

验证方法：提取前几个系数，与直接计算的结果对比。

陷阱3：指数生成函数的混淆

不要将普通生成函数和指数生成函数混用。它们适用于不同类型的组合问题。

经验法则：如果问题涉及排列或带标签的对象，考虑使用EGF；否则使用OGF。

陷阱4：忽略初始条件

在求解递推关系时，忘记正确处理初始条件会导致错误的生成函数方程。

检查方法：将求得的生成函数展开，验证前几项是否符合初始条件。

7.3 与其他领域的联系

信号处理：Z变换是生成函数的离散版本
量子力学：路径积分与生成函数有关
统计学：矩母函数、特征函数都是生成函数的变体
控制理论：传递函数本质上是生成函数
热力学：配分函数可以看作是一种生成函数
语言学：形式语言理论中使用生成函数分析文法

四、代码实战

7.1 生成函数操作库

python

import sympy as sp
from sympy import series, expand, apart, sqrt

class GeneratingFunctions:
    """生成函数工具"""
    
    @staticmethod
    def fibonacci_gf():
        """斐波那契数列的生成函数"""
        x = sp.Symbol('x')
        gf = x / (1 - x - x**2)
        return sp.simplify(gf)
    
    @staticmethod
    def catalan_gf():
        """卡特兰数的生成函数"""
        x = sp.Symbol('x')
        gf = (1 - sqrt(1 - 4*x)) / (2*x)
        return sp.simplify(gf)
    
    @staticmethod
    def geometric_gf(a, r):
        """等比数列 a, ar, ar^2, ... 的生成函数"""
        x = sp.Symbol('x')
        return a / (1 - r*x)
    
    @staticmethod
    def extract_coefficient(gf, var, n):
        """提取生成函数中 x^n 的系数"""
        # 使用series展开
        ser = series(gf, var, 0, n+1).removeO()
        coeff = sp.expand(ser).coeff(var, n)
        return sp.simplify(coeff)
    
    @staticmethod
    def partial_fraction_decomposition(gf, var):
        """部分分式分解"""
        return apart(gf, var)
    
    @staticmethod
    def solve_linear_recurrence(coeffs, initials, n_terms=10):
        """
        求解线性递推关系
        参数:
            coeffs: 递推系数 [c1, c2, ..., ck] 对应 a_n = c1*a_{n-1} + ... + ck*a_{n-k}
            initials: 初始值 [a0, a1, ..., a_{k-1}]
            n_terms: 返回的项数
        """
        k = len(coeffs)
        x = sp.Symbol('x')
        
        # 构建生成函数方程
        # A(x) - sum(initial_i * x^i) = sum(c_j * x^j * (A(x) - sum(initial_i * x^i for i < j)))
        
        # 简化：直接计算前几项
        a = list(initials)
        for n in range(k, n_terms):
            val = sum(coeffs[j] * a[n-j-1] for j in range(k))
            a.append(val)
        return a
    
    @staticmethod
    def bell_egf():
        """贝尔数的指数生成函数"""
        x = sp.Symbol('x')
        return sp.exp(sp.exp(x) - 1)
    
    @staticmethod
    def derangement_egf():
        """错排数的指数生成函数"""
        x = sp.Symbol('x')
        return sp.exp(-x) / (1 - x)
    
    @staticmethod
    def binomial_gf(n):
        """二项式系数 C(n,k) 的生成函数 (1+x)^n"""
        x = sp.Symbol('x')
        return (1 + x)**n

# 测试
gf = GeneratingFunctions()
x = sp.Symbol('x')

print("=== 生成函数测试 ===")

fib_gf = gf.fibonacci_gf()
print(f"斐波那契生成函数: {fib_gf}")

cat_gf = gf.catalan_gf()
print(f"卡特兰数生成函数: {cat_gf}")

# 提取斐波那契数的前几项
print("\n斐波那契数:")
for n in range(10):
    coeff = gf.extract_coefficient(fib_gf, x, n)
    print(f"F_{n} = {coeff}")

# 提取卡特兰数的前几项
print("\n卡特兰数:")
for n in range(8):
    coeff = gf.extract_coefficient(cat_gf, x, n)
    print(f"C_{n} = {coeff}")

# 部分分式分解
gf_rational = 1 / ((1-x)*(1-2*x))
decomposed = gf.partial_fraction_decomposition(gf_rational, x)
print(f"\n部分分式分解: {decomposed}")

# 验证分解后的系数
print("\n验证系数:")
for n in range(6):
    coeff_orig = gf.extract_coefficient(gf_rational, x, n)
    coeff_decomp = gf.extract_coefficient(decomposed, x, n)
    print(f"a_{n}: 原={coeff_orig}, 分解后={coeff_decomp}")

# 求解线性递推
print("\n线性递推 a_n = 3a_{n-1} - 2a_{n-2}, a0=1, a1=2:")
result = gf.solve_linear_recurrence([3, -2], [1, 2], 8)
print(f"前8项: {result}")

# 贝尔数
print("\n贝尔数的前几项:")
bell_egf = gf.bell_egf()
for n in range(8):
    # EGF的系数需要乘以 n!
    coeff = gf.extract_coefficient(bell_egf, x, n)
    bell_n = coeff * sp.factorial(n)
    print(f"B_{n} = {bell_n}")

7.2 FFT加速的多项式乘法

python

import numpy as np

def fft_multiply(poly1, poly2):
    """使用FFT进行多项式乘法"""
    n = len(poly1) + len(poly2) - 1
    # 填充到2的幂
    m = 1
    while m < n:
        m <<= 1
    
    # FFT
    f1 = np.fft.fft(poly1, m)
    f2 = np.fft.fft(poly2, m)
    
    # 点乘
    f_prod = f1 * f2
    
    # 逆FFT
    prod = np.fft.ifft(f_prod)
    
    # 取实部并四舍五入
    result = [int(round(prod[i].real)) for i in range(n)]
    return result

def naive_multiply(poly1, poly2):
    """朴素的多项式乘法 O(n^2)"""
    n = len(poly1) + len(poly2) - 1
    result = [0] * n
    for i, a in enumerate(poly1):
        for j, b in enumerate(poly2):
            result[i+j] += a * b
    return result

# 测试
poly1 = [1, 2, 3]  # 1 + 2x + 3x^2
poly2 = [4, 5]     # 4 + 5x

result_fft = fft_multiply(poly1, poly2)
result_naive = naive_multiply(poly1, poly2)

print(f"\nFFT多项式乘法:")
print(f"({poly1}) * ({poly2}) = {result_fft}")
print(f"朴素乘法结果: {result_naive}")
# 手动验证: (1+2x+3x^2)(4+5x) = 4+5x+8x+10x^2+12x^2+15x^3 = 4+13x+22x^2+15x^3

# 性能比较
import time

# 大规模测试
size = 10000
p1 = np.random.randint(0, 100, size)
p2 = np.random.randint(0, 100, size)

start = time.time()
r_fft = fft_multiply(p1, p2)
time_fft = time.time() - start

start = time.time()
r_naive = naive_multiply(p1[:100], p2[:100])  # 只用小规模测试朴素算法
time_naive = time.time() - start

print(f"\n性能比较 (size={size}):")
print(f"FFT时间: {time_fft:.4f}秒")
print(f"朴素乘法时间 (size=100): {time_naive:.4f}秒")

7.3 概率生成函数

python

def probability_generating_function(pmf, z):
    """计算概率生成函数 G(z) = E[z^X]"""
    return sum(p * z**k for k, p in enumerate(pmf))

def expected_value_from_pgf(pmf):
    """从概率生成函数计算期望值 E[X] = G'(1)"""
    # 数值微分
    z = 1.0
    h = 1e-6
    g1 = probability_generating_function(pmf, z)
    g2 = probability_generating_function(pmf, z + h)
    return (g2 - g1) / h

def variance_from_pgf(pmf):
    """从概率生成函数计算方差 Var(X) = G''(1) + G'(1) - [G'(1)]^2"""
    z = 1.0
    h = 1e-6
    
    # 一阶导数
    g1 = probability_generating_function(pmf, z)
    g2 = probability_generating_function(pmf, z + h)
    g_prime = (g2 - g1) / h
    
    # 二阶导数
    g0 = probability_generating_function(pmf, z - h)
    g_double_prime = (g2 - 2*g1 + g0) / (h**2)
    
    return g_double_prime + g_prime - g_prime**2

# 测试：二项分布 B(5, 0.5)
from math import comb
n_trials = 5
p_success = 0.5
pmf = [comb(n_trials, k) * p_success**k * (1-p_success)**(n_trials-k) for k in range(n_trials+1)]

E_X = expected_value_from_pgf(pmf)
Var_X = variance_from_pgf(pmf)

print(f"\n二项分布 B({n_trials}, {p_success}) 的期望值: {E_X:.4f}")
print(f"理论值: {n_trials * p_success}")
print(f"计算方差: {Var_X:.4f}")
print(f"理论方差: {n_trials * p_success * (1-p_success)}")

# 测试：泊松分布
def poisson_pmf(lam, k):
    return lam**k * np.exp(-lam) / np.math.factorial(k)

lam = 3.0
pmf_poisson = [poisson_pmf(lam, k) for k in range(20)]

E_poisson = expected_value_from_pgf(pmf_poisson)
Var_poisson = variance_from_pgf(pmf_poisson)

print(f"\n泊松分布 Poisson({lam}) 的期望值: {E_poisson:.4f}")
print(f"计算方差: {Var_poisson:.4f}")

7.4 生成函数求解整数划分

python

def partition_generating_function(max_n):
    """
    计算整数划分的生成函数
    P(x) = product_{k=1}^{inf} 1/(1-x^k)
    """
    x = sp.Symbol('x')
    # 截断到 max_n 项
    product = 1
    for k in range(1, max_n + 1):
        product *= 1 / (1 - x**k)
    
    # 展开并提取系数
    series_expansion = series(product, x, 0, max_n + 1).removeO()
    
    partitions = []
    for n in range(max_n + 1):
        coeff = sp.expand(series_expansion).coeff(x, n)
        partitions.append(int(coeff))
    
    return partitions

# 计算前20个整数划分数
partitions = partition_generating_function(20)
print("\n整数划分数:")
for n, p in enumerate(partitions):
    print(f"p({n}) = {p}")

五、深入思考

5.1 历史背景

生成函数的思想可以追溯到欧拉和拉普拉斯。亚伯拉罕·德·莫弗尔早期使用了类似的方法。赫伯特·威尔夫的《生成函数论》（generatingfunctionology）是现代经典参考书，该书免费在线可用。高德纳在《计算机程序设计艺术》中广泛使用了生成函数分析算法。

欧拉在研究整数划分时首次系统地使用了生成函数。他发现整数划分的生成函数是无穷乘积 $\prod_{k=1}^{\infty} \frac{1}{1-x^k}$，这一发现开启了组合分析的新纪元。

拉普拉斯在概率论中引入了矩母函数，这本质上是概率生成函数的连续版本。这一思想后来被切尔诺夫等人发展为切尔诺夫界，成为概率分析的重要工具。

5.2 未解决的问题

非线性递推：大多数非线性递推没有通用的生成函数解法

多变量生成函数：高维情况的理论仍不完善

算法自动化：如何自动识别和求解生成函数方程

超越函数的系数提取：对于复杂的超越函数，如何高效提取系数

渐近分析的自动化：如何从生成函数自动推导系数的渐近行为

5.3 延伸阅读

《generatingfunctionology》 - Herbert Wilf（免费在线可用）

《具体数学》第7章 - Graham, Knuth, Patashnik

《Analytic Combinatorics》 - Philippe Flajolet and Robert Sedgewick

《The Art of Computer Programming, Vol. 1》 - Donald Knuth

《Concrete Mathematics》 - Graham, Knuth, Patashnik

《Combinatorial Species and Tree Structures》 - Bergeron, Labelle, Leroux

六、实验笔记

实验一：生成函数求解递推

目标：使用生成函数求解一个新的递推关系。

问题：求解 aₙ = 4aₙ₋₁ - 4aₙ₋₂，a₀=1, a₁=3。

步骤：

设 A(x) = Σ aₙxⁿ

建立方程并求解 A(x)

部分分式分解

提取系数

预期结果：aₙ = (n+1)2ⁿ⁻¹（需要验证）

详细推导：

A(x) - 1 - 3x = 4x(A(x) - 1) - 4x²A(x)
A(x)(1 - 4x + 4x²) = 1 - x
A(x) = (1-x)/(1-2x)²
部分分式：A(x) = 1/(2(1-2x)) + 1/(2(1-2x)²)
展开：aₙ = 2ⁿ⁻¹/2 + (n+1)2ⁿ⁻¹/2 = (n+2)2ⁿ⁻²

实验二：FFT加速卷积

目标：实现FFT-based多项式乘法，验证生成函数卷积的效率。

步骤：

实现朴素 O(n²) 卷积

实现 FFT-based O(n log n) 卷积

比较不同规模下的运行时间

分析加速比

预期结果：对于大规模输入，FFT应显著快于朴素算法。

实验三：概率生成函数验证

目标：使用概率生成函数验证常见分布的期望和方差。

步骤：

定义二项分布、泊松分布的PMF

计算概率生成函数

通过微分计算期望和方差

与理论值比较

扩展：尝试几何分布、负二项分布。

实验四：卡特兰数的多种推导

目标：通过不同方法推导卡特兰数的闭合形式。

方法：

生成函数法（本章内容）

反射原理（组合证明）

Dyck路径计数

栈的输出序列计数

目标：理解不同方法之间的联系。

七、本章小结

关键概念：

普通生成函数：$A(x) = \sum a_n x^n$
指数生成函数：$\hat{A}(x) = \sum a_n \frac{x^n}{n!}$
卷积：$c_n = \sum_{k=0}^{n} a_k b_{n-k}$
部分分式分解：从有理函数提取系数
指数公式：连通结构与集合划分的关系

核心技巧：

将递推转化为生成函数方程

部分分式分解提取系数

识别常见生成函数模式

区分OGF和EGF的适用场景

利用卷积的组合意义简化计数

实用建议：

对于线性递推，生成函数方法总是有效
对于非线性递推，可能需要创造性思维
FFT可以加速大规模卷积计算
概率生成函数是分析随机变量的有力工具
多变量生成函数可以处理更复杂的计数问题

进阶主题：

解析组合学：使用复分析研究生成函数的奇点
形式幂级数算法：高效的符号计算
q-模拟：生成函数的量子推广

八、习题

基础题

习题 7.1：求序列 1, 3, 9, 27, ... 的生成函数。

提示：这是公比为3的等比数列。

解答：$\sum_{n=0}^{\infty} 3^n x^n = \frac{1}{1-3x}$

习题 7.2：用生成函数求解 aₙ = 2aₙ₋₁ + 1，a₀ = 0。

提示：设 A(x) = Σ aₙxⁿ，建立方程。

解答：A(x) = x/((1-x)(1-2x))，展开得 aₙ = 2ⁿ - 1。

习题 7.3：求序列 0, 1, 4, 9, 16, ...（即 aₙ = n²）的生成函数。

提示：从 $\frac{1}{1-x} = \sum x^n$ 出发，通过微分和乘法得到。

解答：$\frac{x(1+x)}{(1-x)^3}$

进阶题

习题 7.4：[ME] 推导 Bell 数的生成函数 $e^{e^x-1}$。

提示：使用指数公式，考虑集合划分的组合结构。

习题 7.5：[ME] 用生成函数证明范德蒙德卷积 $\sum_{k} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$。

提示：考虑 (1+x)ᵐ(1+x)ⁿ = (1+x)ᵐ⁺ⁿ。

习题 7.6：[ME] 求解递推关系 aₙ = 5aₙ₋₁ - 6aₙ₋₂，a₀=1, a₁=2。

提示：生成函数为 $\frac{1-3x}{1-5x+6x^2}$，部分分式分解。

解答：aₙ = 2ⁿ。

挑战题

习题 7.7：[HM25] 研究多变量生成函数及其在组合计数中的应用。

提示：考虑二元生成函数 A(x,y) = Σ a_{m,n} x^m y^n。

习题 7.8：[HM30] 用复分析方法推导卡特兰数的渐近公式 $C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$。

提示：使用 saddle-point 方法或 singularity analysis。

习题 7.9：[HM35] 证明错排数的EGF为 $\frac{e^{-x}}{1-x}$。

提示：利用排列 = 错排 ∪ 固定点的分解。

习题 7.10：[HM40] 研究生成函数在算法分析中的应用，特别是快速排序的平均情况分析。

提示：快速排序的比较次数满足递推关系，可以用生成函数求解。

习题 7.11：[HM20] 推导整数划分生成函数 $\prod_{k=1}^{\infty} \frac{1}{1-x^k}$ 的前20项系数。

提示：使用动态规划或符号计算软件。

本章完

第7章 生成函数 (Generating Functions)

一、导读

7.1 本章学习目标

7.2 为什么本章如此重要

7.3 核心问题引导

二、核心概念详解

7.1 生成函数的定义

普通生成函数

指数生成函数

狄利克雷生成函数

7.2 基本操作的组合意义

加法

乘法（卷积）

移位

微分

积分

复合

Hadamard积

7.3 求解递推关系

示例1：斐波那契数列

示例2：线性递推

示例3：非齐次递推

7.4 卡特兰数的生成函数

7.5 部分分式分解

7.6 指数生成函数的应用

7.7 生成函数的其他类型

狄利克雷生成函数

朗伯级数

7.8 多变量生成函数

三、程序员的视角

7.1 在算法中的应用

多项式乘法

动态规划优化

概率生成函数

形式幂级数算法

7.2 常见陷阱

陷阱1：收敛性问题

陷阱2：系数提取错误

陷阱3：指数生成函数的混淆

陷阱4：忽略初始条件

7.3 与其他领域的联系

四、代码实战

7.1 生成函数操作库

7.2 FFT加速的多项式乘法

7.3 概率生成函数

7.4 生成函数求解整数划分

五、深入思考

5.1 历史背景

5.2 未解决的问题

5.3 延伸阅读

六、实验笔记

实验一：生成函数求解递推

实验二：FFT加速卷积

实验三：概率生成函数验证

实验四：卡特兰数的多种推导

七、本章小结

八、习题

基础题

进阶题

挑战题

第7章生成函数 (Generating Functions)