生成函数

参考资料

• 普通生成函数 - OI Wiki
• 指数生成函数 - OI Wiki

普通生成函数

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

$$F(x)=\sum_n a_nx^n$$

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

基本运算

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

$$F(x)\pm G(x)=\sum_n (a_n\pm b_n)x^n$$

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

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

$$F(x)G(x)=\sum_n x^n\sum_{i=0}^na_ib_{n-i}$$

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

指数生成函数

指数生成函数（EGF）把数列 $\set{a_n}$ 对应到 $\sum_{n\ge 0} a_n\frac{x^n}{n!}$，适合「有标号」组合对象的计数。两个 EGF 相乘对应有标号对象的合并并自带组合系数；配合多项式 $\exp$，可由「连通对象」的 EGF 推出「任意对象」的 EGF。

例题

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

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