专栏文章

生成函数基础

yyemuzhe
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min060n1
此快照首次捕获于
2025/12/01 18:24
3 个月前
此快照最后确认于
2025/12/01 18:24
3 个月前
查看原文

普通生成函数（OGF）

一般用于无标号计数的代数推导。
令形式幂级数 F=∑n=0anxnF = \sum _ {n = 0} a _ n x ^ n，则 FF 被称为原序列 (a0,a1,a2,…)(a _ 0, a _ 1, a _ 2, \ldots) 的普通生成函数。
我们可以在一个生成函数 FF 和一个序列 (a0,a1,a2,…)(a _ 0, a _ 1, a _ 2, \ldots) 间建立双射关系，这样有利于把序列转成函数来推导。

基本运算

加法：(A+B)n=An+Bn(A + B) _ n = A _ n + B _ n
标量乘法：(cA)n=cAn(cA) _ n = cA _ n
卷积乘法：(AB)n=∑i=0nAiBn−i(AB) _ n = \sum _ {i = 0} ^ n A _ i B _ {n - i}

封闭形式

封闭形式可以理解为把一个函数化为一个等效的数来参与运算。
普通生成函数的常见封闭形式有：
  1. ∑n=0xn=11−x\sum _ {n = 0} x ^ n = \frac 1 {1 - x}
    证明：
    令 S=∑n=0xnS = \sum _ {n = 0} x ^ n，
    则 xS=∑n=1xnxS = \sum _ {n = 1} x ^ n
    二式相减，得 (1−x)S=1(1 - x)S = 1，从而 S=11−xS = \frac 1 {1 - x}
  2. ∑n=kxn=xk1−x\sum _ {n = k} x ^ n = \frac {x ^ k} {1 - x}
    证明：
    令 S=∑n=kxnS = \sum _ {n = k} x ^ n，
    则 xS=∑n=k+1xnxS = \sum _ {n = k + 1} x ^ n
    二式相减，得 (1−x)S=xk(1 - x)S = x ^ k，从而 S=xk1−xS = \frac {x ^ k} {1 - x}
  3. ∑m=0,n=k+mdxn=xk1−xd\sum _ {m = 0, n = k + md} x ^ n = \frac {x ^ k} {1 - x ^ d}
    证明：
    令 S=∑m=0,n=k+mdxnS = \sum _ {m = 0, n = k + md} x ^ n，
    则 xdS=∑m=1,n=k+mdxnx ^ dS = \sum _ {m = 1, n = k + md} x ^ n
    二式相减，得 (1−xd)S=xk(1 - x ^ d)S = x ^ k，从而 S=xk1−xdS = \frac {x ^ k} {1 - x ^ d}
  4. ∑n=0(1−G)n=1G\sum _ {n = 0} (1 - G) ^ n = \frac 1 G，其中 GG 是一个关于 xx 的多项式。
    证明：
    同 11，这个式子经常用来展开封闭形式。
  5. ∑n=0(mn)xn=(1+x)m\sum _ {n = 0} \binom m n x ^ n = (1 + x) ^ m
    证明：
    其实就是二项式定理。
  6. ∑n=0(n+1)xn=1(1−x)2\sum _ {n = 0} (n + 1) x ^ n = \frac 1 {(1 - x) ^ 2}
    证明：
    令 F(x)=∑n=0xn=11−xF (x) = \sum _ {n = 0} x ^ n = \frac 1 {1 - x}
    求导，得 F′(x)=∑n=0(n+1)xn=(11−x)′=(−1(1−x)2)⋅(−1)=1(1−x)2F ^ \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. ∑n=0nxn=x(1−x)2\sum _ {n = 0} n x ^ n = \frac x {(1 - x) ^ 2}
    证明：
    由 66 中 F′(x)−F(x)F ^ \prime (x) - F (x) 可得 ∑n=0nxn=1(1−x)2−11−x=x(1−x)2\sum _ {n = 0} n x ^ n = \frac 1 {(1 - x) ^ 2} - \frac 1 {1 - x} = \frac x {(1 - x) ^ 2}
  8. ∑n=0(n+mm)xn=1(1−x)m+1\sum _ {n = 0} \binom {n + m} m x ^ n = \frac 1 {(1 - x) ^ {m + 1}}
    证明：
    由 11，当 m=0m = 0 时，原式显然成立，故接下来讨论 m≥1m \ge 1 的情况。
    考虑数学归纳法，设当前已知 F(x)=∑n=0(n+m−1m−1)xn=1(1−x)mF (x) = \sum _ {n = 0} \binom {n + m - 1} {m - 1} x ^ n = \frac 1 {(1 - x) ^ m}
    则 F′(x)=(1(1−x)m)′=(−m⋅1(1−x)m+1)⋅(−1)=m⋅1(1−x)m+1F ^ \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′(x)=∑n=1(n+m−1m−1)nxn−1F ^ \prime (x) = \sum _ {n = 1} \binom {n + m - 1} {m - 1} n x ^ {n - 1}
    由 (n+m−1m−1)=(n+m−1m)⋅mn\binom {n + m - 1} {m - 1} = \binom {n + m - 1} m \cdot \frac m n，得
    F′(x)=∑n=1(n+m−1m)mxn−1=m∑n=0(n+mm)xnF ^ \prime (x) = \sum _ {n = 1} \binom {n + m - 1} m m x ^ {n - 1} = m \sum _ {n = 0} \binom {n + m} m x ^ n
    故 ∑n=0(n+mm)xn=1mF′(x)=1(1−x)m+1\sum _ {n = 0} \binom {n + m} m x ^ n = \frac 1 m F ^ \prime (x) = \frac 1 {(1 - x) ^ {m + 1}}
  9. ∑n=11nxn=−ln⁡(1−x)\sum _ {n = 1} \frac 1 n x ^ n = -\ln (1 - x)
    证明：
    考虑泰勒展开，即令 F(x)=−ln⁡(1−x)F (x) = - \ln (1 - x)，则 F(x)=∑n=0F(n)(0)n!xn=∑n=0(n−1)!n!=∑n=01nxnF (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,… )Fib = (0, 1, 1, 2, 3, 5, \dots)，设其生成函数为 F(x)F (x)，则
F(x)=x+xF(x)+x2F(x)F (x) = x + x F (x) + x ^ 2 F (x)
解得 F(x)=x1−x−x2F (x) = \frac x {1 - x - x ^ 2}
这种形式不便于展开，考虑拆成两项相加形式。
设 x1−x−x2=a1−bx+c1−dx\frac x {1 - x - x ^ 2} = \frac a {1 - bx} + \frac c {1 - dx}，解得
{a=55b=1+52c=−55d=1−52\begin {cases} a = \frac {\sqrt 5} 5 \\ b = \frac {1 + \sqrt 5} 2 \\ c = -\frac {\sqrt 5} 5 \\ d = \frac {1 - \sqrt 5} 2 \end {cases}
代回去，得到 F(x)=55(11−1+52x−11−1−52x)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)
展开成形式幂级数，得
F(x)=55∑n=0((1+52)n−(1−52)n)xnF (x) = \frac {\sqrt 5} 5 \sum _ {n = 0} \left (\left(\frac {1 + \sqrt 5} 2\right) ^ n - \left(\frac {1 - \sqrt 5} 2\right) ^ n\right) x ^ n
故 Fibn=[xn]F(x)=55((1+52)n−(1−52)n)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=∑n=0anxnn!F = \sum _ {n = 0} a _ n \frac {x ^ n} {n!}，则 FF 被称为原序列 (a0,a1,a2,…)(a _ 0, a _ 1, a _ 2, \ldots) 的指数生成函数。

基本运算

加法：(A+B)i=Ai+Bi(A + B) _ i = A _ i + B _ i
标量乘法：(cA)i=cAi(cA) _ i = cA _ i
卷积乘法：(AB)i=∑i=0n(ni)AiBn−i(AB) _ i = \sum _ {i = 0} ^ n \binom n i A _ i B _ {n - i}
EGF 转 OGF：Gi=1n!FiG _ i = \frac 1 {n!} F _ i
OGF 转 EGF：Fi=n!GiF _ i = n! G _ i
其中，EGF 与 OGF 的互相转化只是为了将 EGF 的卷积转成普通卷积，方便 NTT 优化。
注意到 EGF 的卷积自带组合数，所以 EGF 能解决有标号问题。相当于如果把一个 EGF 看成一个集合，那么若干 EGF 相乘就相当于把 1∼n1 \sim n 划分到这些集合中，再乘上对应的系数。

封闭形式

  1. ∑n=0xnn!=ex\sum _ {n = 0} \frac {x ^ n} {n!} = e ^ x
    证明：
    考虑泰勒展开，即令 F(x)=exF (x) = e ^ x，则 F(x)=∑n=0F(n)(0)n!xn=∑n=01n!xn=∑n=0xnn!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. ∑n=0anxnn!=eax\sum _ {n = 0} a ^ n \frac {x ^ n} {n!} = e ^ {ax}
    证明：
    同 11，把 xnx ^ n 换成 (ax)n(ax) ^ n 即可。
  3. ∑(n mod d)=kanxnn!=1d∑i=0d−1ωd−ikeωdiax\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]=1d∑i=0d−1ωdin[n | d] = \frac 1 d \sum _ {i = 0} ^ {d - 1} \omega _ d ^ {in}，得 [(n mod d)=k]=[(n−k)∣d]=1d∑i=0d−1ωdi(n−k)[(n \bmod d) = k] = [(n - k) | d] = \frac 1 d \sum _ {i = 0} ^ {d - 1} \omega _ {d} ^ {i(n - k)}
    故 ∑(n mod d)=kanxnn!=∑n=0[(n mod d)=k]anxnn!=∑n=0anxnn!⋅1d∑i=0d−1ωdi(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)}
    =1d∑i=0d−1∑n=0ωdi(n−k)anxnn!=1d∑i=0d−1ωd−ikeωdiax= \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}

一些运算的组合意义

令 FF 为一个集合的 EGF。
  1. 把 nn 个有标号的点划分进 mm 个有标号的集合：
    G=FmG = F ^ m
  2. 把 nn 个有标号的点划分进 mm 个无标号的集合：
    G=Fmm!G = \frac {F ^ m} {m!}
  3. 把 nn 个有标号的点划分进若干个有标号的集合：
    G=11−FG = \frac 1 {1 - F}
    证明：
    枚举集合数 ii，则 G=∑i=0Fi=11−FG = \sum _ {i = 0} F ^ i = \frac 1 {1 - F}
  4. 把 nn 个有标号的点划分进若干个无标号的集合：
    G=exp⁡(F)G = \exp (F)
    证明：
    枚举集合数 ii，则 G=∑i=0Fii!=exp⁡(F)G = \sum _ {i = 0} \frac {F ^ i} {i!} = \exp (F)
ln⁡(F)\ln (F) 的意义：若 F=exp⁡(G)F = \exp (G)，则 G=ln⁡(F)G = \ln (F)
从组合意义上来讲，相当于是知道划分后的 EGF，倒推一个集合的 EGF。

想做题了？

推荐个人题目练习题单。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...