普通生成函数
2026-05-12
定义
对于一个离散的数列 a,定义它的普通生成函数为:
A(x)=n=0∑∞anxn=a0+a1x+a2x2+⋯
对于算法竞赛而言,我们不考虑收敛域的问题,这里的 x 仅是一个占位符,我们真正关心的是如何将 xk 的系数 ak 取出来。
麦克劳林展开
如果已经知道 A(x) 的具体表达式,怎么求 ak?
- 对于 a0,显然只需要将 x=0 就可以了。
- 对于 a1,先对 A 求一阶导数 A′,再代入 x=0 即可。
以此类推,想要提取 ak 就需要对 A 一直求导,那么 akxk 这一项的系数会受到 k×(k−1)×⋯×1=k! 的连乘。
综上,对于一个在 x=0 处无穷可导的函数 f(x),都可以展开为无穷多项式,且第 n 项的系数为:
an=n!f(n)(0)
这就是麦克劳林展开。
封闭形式
我们已经了解了生成函数的展开,那么有没有简短一点的形式呢?有的有的,就是封闭形式。
我们以 {1,1,⋯,1} 为例,它的普通生成函数为 F(x)=∑n=0∞xn,可以发现有 F(x)x+1=F(x),解这个方程得到 F(x)=1−x1,也就是这个 OGF 的封闭形式。
代数操作
两个生成函数相加减,等于对应序列系数相加减:
A(x)±B(x)=n=0∑∞(an±bn)xn
一个序列平移,将整体提升 xk:
xk×A(x)=n=0∑∞anxn+k=n=0∑∞an−kxn
两个生成函数相乘,相当于原序列的离散卷积:
A(x)B(x)=n=0∑∞(i=0∑naibn−i)xn
一个序列 A 进行前缀和操作,考虑将序列 A 与 B={1,1,⋯,1} 相乘,得到:
A(x)⋅1−x1=n=0∑∞(i=0∑nai)xn
容易发现,每个 xi 的系数恰好变成了 ∑ai。
一个序列每一项乘其下标,即原序列变成 {0×a0,1×a1x,2×a2x2,⋯,i×aixi},考虑先对 A 求导,在乘 x 进行补位:
xA′(x)=xn=1∑∞n⋅anxn−1=n=0∑∞n⋅anxn
斐波那契数列的生成函数
已知 f0=1,f1=0,且 ∀n≥2,fn=fn−1+fn−2,求 fn 生成函数封闭形式及其通项公式。
令 F(x)=∑n=0∞fnxn,根据递推式构造生成函数:
F(x)xF(x)x2F(x)=f0=0=0+++f1f0x0+++n=2∑∞fnxnn=2∑∞fn−1xnn=2∑∞fn−2xn
将上式带入递推关系 F(x)−xF(x)−x2F(x) 进行消项,得到 x,提取公因式后解得封闭形式:
F(x)=1−x−x21
得到了封闭形式,我们来尝试将其展开,首先进行因式分解,即 1−x−x2=(1−αx)(1−βx),得到 α=21+5,β=21−5,带入原式后拆分为常用的等比数列求和形式:
F(x)=(1−αx)(1−βx)x=1−αxA+1−βxB
通过待定系数,得到 A=51,B=−51,然后带入原式并进行展开:
F(x)=51(n=0∑∞αnxn−n=0∑∞βnxn)=n=0∑∞51(αn−βn)xn
由此,我们得到斐波那契数列的通项公式:
fn=51[(21+5)n−(21−5)n]
生成函数乘法与排列组合
假设我们有两个物品集合 A 和 B,集合 A 有一种总重量为 i 的选取方案记为 xi,同样地 B 有一种总重量为 j 的选取方案 xj,如果我们将两个选择合并,总重量 i+j,恰好对应代数乘法 xi⋅xj=xi+j。
一些选取模型:
- 无限制,可选任意多个:
1+x+x2+⋯=1−x1 - 最多选取 k 个:
1+x+x2+⋯+xk=1−x1−xk+1
上式可以从等比数列求和或组合意义(选取任意多个减去选取多于 k 个的)得到。 - 只能选取偶数个:
1+x2+x4+⋯=1−x21
上式可以从无限制选取推得。 - 只能选取 k 的倍数个:
1+xk+x2k+⋯=1−xk1
生成函数与背包 DP
如果我们将背包容量放在 x 的次数上,可以得到:
- 0/1 背包:1+xw。
- 完全背包:1+xw+x2w+⋯=1−xw1
- 多重背包:1+xw+x2w+⋯xkw=1−xw1−x(k+1)w
生成函数与盒子
将 n 个球放入 m 个盒子,允许空盒,求方案数。
对于 OGF 而言,每个盒子可以放 0,1,2,⋯ 个球,即 1−x1,盒子相互独立,即:
G(x)=(1−x1)m=(1−x)−m
这就是广义二项式定理的形式,直接带入:
an=(nm+n−1)
这与隔板法是一样的。
将 n 个球放入 m 个盒子,每个盒最多 k 个,允许空盒求方案数。
对于 OGF 而言,每个盒子可以放 0,1,2,⋯,k 个球,即 1−x1−xk+1,总生成函数即为:
G(x)=(1−x1−xk+1)m=(1−xk+1)m⋅(1−x)−m
此时求系数只需要前面二项式定理后面广义二项式定理即可。
