指数生成函数
2026-05-17
引入
在普通生成函数的组合问题中,我们只是简单的将重量相加,没有考虑顺序的问题,如果想从 A 中选若干个不同的物品,B 中选若干个不同的物品将其排成一列该怎么办呢?
定义
对于一个离散的序列 a,我们定义它的指数生成函数为:
A(x)=n=0∑∞ann!xn=a0+a11!x+a22!x2+…
乘法运算
如果将 EGF A 和 B 相乘,会怎么样呢:
A(x)B(x)=(i=0∑∞aii!xi)(j=0∑∞bjj!xj)
考虑 i+j=n:
i=0∑ni!ai(n−i)!bn−ixn=i=0∑n(i!(n−i)!n!aibn−i)n!xn=i=0∑n(in)aibn−in!xn
也就是说,两个 EGF 相乘会自动附带二项式系数 (in) 也就顺带解决了有序合并的穿插问题。
EGF 与排列组合
无限制:
∑n=0∞1⋅n!xn=ex至少取 1 个(非空):
∑n=1∞1⋅n!xn=ex−1只能取偶数个:
利用 (−x)n 的正负号交替性质消去奇数项。
2ex+e−x=1+2!x2+4!x4+⋯只能取奇数个:
2ex−e−x=1!x+3!x3+…
EGF 与第二类斯特林数
将 n 个不同的球放入 k 个相同的盒子且没有空盒的方案数成为第二类斯特林数,记作 {kn} 或 S(n,k)。
考虑球相同的一个非空盒子的 EGF 显然是 ex−1,有 k 个盒子则对应的 EGF 应为 (ex−1)k,又因为盒子不同,所以总生成函数为:
S(x)=k!(ex−1)k
有了生成函数,我们考虑提取 n!xn 的系数。
先用二项式定理展开:
(ex−1)k=i=0∑k(ik)(ex)i(−1)k−i=i=0∑k(ik)(−1)k−ieix
将 eix 用麦克劳林展开:
eix=n=0∑∞n!(ix)n=n=0∑∞inn!xn
带回原式,得到:
k!(ex−1)k=k!1i=0∑k(ik)(−1)k−in=0∑∞inn!xn
交换其中的求和顺序,得到:
{kn}=k!1i=0∑k(−1)k−i(ik)in
这个式子可以 O(klogn) 处理。
