Skip to main content

生成函数

Summary

生成函数把数列编码为形式幂级数的系数，用函数运算刻画数列变换。普通生成函数（OGF）定义为数列各项乘对应幂次再求和，其加减对应逐项加减、乘法对应卷积。指数生成函数（EGF）在每项上多除以一个阶乘，乘法给出带二项式系数的卷积，恰对应有标号组合对象合并时的标号分配方案数，因而适合刻画有标号计数。给出两类生成函数的定义与加、乘运算公式。例题为洛谷 P4841。

参考资料​

普通生成函数​

序列 aa 的普通生成函数（Ordinary Generating Function，OGF）定义为形式幂级数：

F(x)=∑nanxnF(x)=\sum_n a_nx^n

换句话说，如果序列 aa 有通项公式，那么它的普通生成函数的系数就是通项公式。

基本运算​

考虑两个序列 a,ba,b 的普通生成函数，分别为 F(x),G(x)F(x),G(x)。那么有：

F(x)±G(x)=∑n(an±bn)xnF(x)\pm G(x)=\sum_n (a_n\pm b_n)x^n

因此 F(x)±G(x)F(x)\pm G(x) 是序列 ⟨an±bn⟩\langle a_n\pm b_n\rangle 的普通生成函数。

考虑乘法运算，也就是卷积：

F(x)G(x)=∑nxn∑i=0naibn−iF(x)G(x)=\sum_n x^n\sum_{i=0}^na_ib_{n-i}

因此 F(x)G(x)F(x)G(x) 是序列 ⟨∑i=0naibn−i⟩\langle\sum_{i=0}^n a_ib_{n-i}\rangle 的普通生成函数。

指数生成函数​

序列 aa 的指数生成函数（Exponential Generating Function，EGF）定义为形式幂级数：

F^(x)=∑nanxnn!\hat F(x)=\sum_n a_n\frac{x^n}{n!}

相比普通生成函数多了 n!n! 的分母，因此指数生成函数适合刻画「有标号」组合对象的计数。

基本运算​

考虑两个序列 a,ba,b 的指数生成函数，分别为 F^(x),G^(x)\hat F(x),\hat G(x)。那么有：

F^(x)±G^(x)=∑n(an±bn)xnn!\hat F(x)\pm \hat G(x)=\sum_n (a_n\pm b_n)\frac{x^n}{n!}

因此 F^(x)±G^(x)\hat F(x)\pm \hat G(x) 是序列 ⟨an±bn⟩\langle a_n\pm b_n\rangle 的指数生成函数。

考虑乘法运算：

F^(x)G^(x)=∑nxnn!∑i=0n(ni)aibn−i\hat F(x)\hat G(x)=\sum_n \frac{x^n}{n!}\sum_{i=0}^n\binom{n}{i}a_ib_{n-i}

因此 F^(x)G^(x)\hat F(x)\hat G(x) 是序列 ⟨∑i=0n(ni)aibn−i⟩\left\langle\sum_{i=0}^n\binom{n}{i}a_ib_{n-i}\right\rangle 的指数生成函数。乘法中出现的二项式系数 (ni)\binom{n}{i} 恰对应有标号对象合并时的标号分配方案数。

例题​

洛谷 P4841 [集训队作业2013] 城市规划

求 nn 个点的带标号简单连通无向图的个数，对 10045358091004535809 取模。