生成函数基础

yemuzhe · 2025-11-26 09:50:55 · 算法·理论

普通生成函数（OGF）

一般用于无标号计数的代数推导。

令形式幂级数 F = \sum _ {n = 0} a _ n x ^ n，则 F 被称为原序列 (a _ 0, a _ 1, a _ 2, \ldots) 的普通生成函数。

我们可以在一个生成函数 F 和一个序列 (a _ 0, a _ 1, a _ 2, \ldots) 间建立双射关系，这样有利于把序列转成函数来推导。

基本运算

加法：(A + B) _ n = A _ n + B _ n

标量乘法：(cA) _ n = cA _ n

卷积乘法：(AB) _ n = \sum _ {i = 0} ^ n A _ i B _ {n - i}

封闭形式

封闭形式可以理解为把一个函数化为一个等效的数来参与运算。

普通生成函数的常见封闭形式有：

1. \sum _ {n = 0} x ^ n = \frac 1 {1 - x}

   证明：

   令 S = \sum _ {n = 0} x ^ n，

   则 xS = \sum _ {n = 1} x ^ n

   二式相减，得 (1 - x)S = 1，从而 S = \frac 1 {1 - x}

2. \sum _ {n = k} x ^ n = \frac {x ^ k} {1 - x}

   证明：

   令 S = \sum _ {n = k} x ^ n，

   则 xS = \sum _ {n = k + 1} x ^ n

   二式相减，得 (1 - x)S = x ^ k，从而 S = \frac {x ^ k} {1 - x}

3. \sum _ {m = 0, n = k + md} x ^ n = \frac {x ^ k} {1 - x ^ d}

   证明：

   令 S = \sum _ {m = 0, n = k + md} x ^ n，

   则 x ^ dS = \sum _ {m = 1, n = k + md} x ^ n

   二式相减，得 (1 - x ^ d)S = x ^ k，从而 S = \frac {x ^ k} {1 - x ^ d}

4. 证明： 同 $1$，这个式子经常用来展开封闭形式。
5. \sum _ {n = 0} \binom m n x ^ n = (1 + x) ^ m

   证明：

   其实就是二项式定理。

6. \sum _ {n = 0} (n + 1) x ^ n = \frac 1 {(1 - x) ^ 2}

   证明：

   令 F (x) = \sum _ {n = 0} x ^ n = \frac 1 {1 - x}

   求导，得 F ^ \prime (x) = \sum _ {n = 0} (n + 1) x ^ n = \left(\frac 1 {1 - x}\right) ^ \prime = \left(- \frac 1 {(1 - x) ^ 2}\right) \cdot (-1) = \frac 1 {(1 - x) ^ 2}

   运用除法法则也可得出相同结果。

7. \sum _ {n = 0} n x ^ n = \frac x {(1 - x) ^ 2}

   证明：

   由 6 中 F ^ \prime (x) - F (x) 可得 \sum _ {n = 0} n x ^ n = \frac 1 {(1 - x) ^ 2} - \frac 1 {1 - x} = \frac x {(1 - x) ^ 2}

8. \sum _ {n = 0} \binom {n + m} m x ^ n = \frac 1 {(1 - x) ^ {m + 1}}

   证明：

   由 1，当 m = 0 时，原式显然成立，故接下来讨论 m \ge 1 的情况。

   考虑数学归纳法，设当前已知 F (x) = \sum _ {n = 0} \binom {n + m - 1} {m - 1} x ^ n = \frac 1 {(1 - x) ^ m}

   则 F ^ \prime (x) = \left(\frac 1 {(1 - x) ^ m}\right) ^ \prime = \left(-m \cdot \frac 1 {(1 - x) ^ {m + 1}}\right) \cdot (-1) = m \cdot \frac 1 {(1 - x) ^ {m + 1}}

   又 F ^ \prime (x) = \sum _ {n = 1} \binom {n + m - 1} {m - 1} n x ^ {n - 1}

   由 \binom {n + m - 1} {m - 1} = \binom {n + m - 1} m \cdot \frac m n，得

   F ^ \prime (x) = \sum _ {n = 1} \binom {n + m - 1} m m x ^ {n - 1} = m \sum _ {n = 0} \binom {n + m} m x ^ n

   故 \sum _ {n = 0} \binom {n + m} m x ^ n = \frac 1 m F ^ \prime (x) = \frac 1 {(1 - x) ^ {m + 1}}

9. \sum _ {n = 1} \frac 1 n x ^ n = -\ln (1 - x)

   证明：

   考虑泰勒展开，即令 F (x) = - \ln (1 - x)，则 F (x) = \sum _ {n = 0} \frac {F ^ {(n)} (0)} {n!} x ^ n = \sum _ {n = 0} \frac {(n - 1)!} {n!} = \sum _ {n = 0} \frac 1 n x ^ n

特征方程

例如斐波那契数列 Fib = (0, 1, 1, 2, 3, 5, \dots)，设其生成函数为 F (x)，则

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

这种形式不便于展开，考虑拆成两项相加形式。

设 \frac x {1 - x - x ^ 2} = \frac a {1 - bx} + \frac c {1 - dx}，解得

代回去，得到 F (x) = \frac {\sqrt 5} 5 \left(\frac 1 {1 - \frac {1 + \sqrt 5} 2 x} - \frac 1 {1 - \frac {1 - \sqrt 5} 2 x}\right)

展开成形式幂级数，得

故 Fib _ n = [x ^ n] F (x) = \frac {\sqrt 5} 5 \left (\left(\frac {1 + \sqrt 5} 2\right) ^ n - \left(\frac {1 - \sqrt 5} 2\right) ^ n\right)

指数生成函数（EGF）

一般用于有标号计数的代数推导。

令形式幂级数 F = \sum _ {n = 0} a _ n \frac {x ^ n} {n!}，则 F 被称为原序列 (a _ 0, a _ 1, a _ 2, \ldots) 的指数生成函数。

基本运算

加法：(A + B) _ i = A _ i + B _ i

标量乘法：(cA) _ i = cA _ i

卷积乘法：(AB) _ i = \sum _ {i = 0} ^ n \binom n i A _ i B _ {n - i}

EGF 转 OGF：G _ i = \frac 1 {n!} F _ i

OGF 转 EGF：F _ i = n! G _ i

其中，EGF 与 OGF 的互相转化只是为了将 EGF 的卷积转成普通卷积，方便 NTT 优化。

注意到 EGF 的卷积自带组合数，所以 EGF 能解决有标号问题。相当于如果把一个 EGF 看成一个集合，那么若干 EGF 相乘就相当于把 1 \sim n 划分到这些集合中，再乘上对应的系数。

封闭形式

1. \sum _ {n = 0} \frac {x ^ n} {n!} = e ^ x

   证明：

   考虑泰勒展开，即令 F (x) = e ^ x，则 F (x) = \sum _ {n = 0} \frac {F ^ {(n)} (0)} {n!} x ^ n = \sum _ {n = 0} \frac 1 {n!} x ^ n = \sum _ {n = 0} \frac {x ^ n} {n!}

2. \sum _ {n = 0} a ^ n \frac {x ^ n} {n!} = e ^ {ax}

   证明：

   同 1，把 x ^ n 换成 (ax) ^ n 即可。

3. \sum _ {(n \bmod d) = k} a ^ n \frac {x ^ n} {n!} = \frac 1 d \sum _ {i = 0} ^ {d - 1} \omega _ d ^ {-ik} e ^ {\omega _ d ^ i ax}

   证明：

   由单位根反演 [n | d] = \frac 1 d \sum _ {i = 0} ^ {d - 1} \omega _ d ^ {in}，得 [(n \bmod d) = k] = [(n - k) | d] = \frac 1 d \sum _ {i = 0} ^ {d - 1} \omega _ {d} ^ {i(n - k)}

   故 \sum _ {(n \bmod d) = k} a ^ n \frac {x ^ n} {n!} = \sum _ {n = 0} [(n \bmod d) = k] a ^ n \frac {x ^ n} {n!} = \sum _ {n = 0} a ^ n \frac {x ^ n} {n!} \cdot \frac 1 d \sum _ {i = 0} ^ {d - 1} \omega _ {d} ^ {i(n - k)}

   = \frac 1 d \sum _ {i = 0} ^ {d - 1} \sum _ {n = 0} \omega _ d ^ {i(n - k)} a ^ n \frac {x ^ n} {n!} = \frac 1 d \sum _ {i = 0} ^ {d - 1} \omega _ d ^ {-ik} e ^ {\omega _ d ^ i ax}

一些运算的组合意义

令 F 为一个集合的 EGF。

1. 把 n 个有标号的点划分进 m 个有标号的集合：

   G = F ^ m

2. 把 n 个有标号的点划分进 m 个无标号的集合：

   G = \frac {F ^ m} {m!}

3. 把 n 个有标号的点划分进若干个有标号的集合：

   G = \frac 1 {1 - F}

   证明：

   枚举集合数 i，则 G = \sum _ {i = 0} F ^ i = \frac 1 {1 - F}

4. 把 n 个有标号的点划分进若干个无标号的集合：

   G = \exp (F)

   证明：

   枚举集合数 i，则 G = \sum _ {i = 0} \frac {F ^ i} {i!} = \exp (F)

从组合意义上来讲，相当于是知道划分后的 EGF，倒推一个集合的 EGF。

想做题了？

推荐个人题目练习题单。