生成函数

参考资料

序列 $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$ 的普通生成函数。

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

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

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

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

\hat F(x)\pm \hat G(x)=\sum_n (a_n\pm b_n)\frac{x^n}{n!}

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

考虑乘法运算：

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

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

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