生成函数入门

前言

A：你知道当 $n$ 很大的时候怎么快速求 $\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\dots+(-1)^n\binom{n}{n}$ 吗？

B：这不是二项式定理的逆运用吗？$(1-1)^n=\sum\limits_{i=0}^n(-1)^i\binom{n}{i}=\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\dots+(-1)^n\binom{n}{n}$，所以原式为 $0$。

上面这种情景其实是经常出现的，很多时候一些数列的操作往往可以被“压缩”成一些简洁式子的运算。

也就是说，可以用函数来表示数列，然后把数列上奇奇怪怪的操作转化为我们熟知的各种运算，最后从运算后的函数还原回数列，求出想要的答案。具体的，可以随便选一些“特征函数”$f_i(x)$，然后定义：

$F(x)=\sum\limits_{i=0}^\infin a_if_i(x)$

为数列 $a$ 的“生成函数”（也可以叫做母函数）。

虽然但是，$f_i(x)$ 并不是怎么指定都可以让 $F(x)$ 有足以解出题目的性质的，所以生成函数也根据 $f_i(x)$ 分为几种。

需要注意的是，$F(x)$ 的参数 $x$ 是无关紧要的，$x$ 取何值并不影响从生成函数还原到数列的过程。所以通常为了令生成函数收敛都会取 $-1<x<1$。

Part 1 普通型生成函数 OGF（$\mathtt{O}$rdinary $\mathtt{G}$enerating $\mathtt{F}$unction）

链接。

Part 2 指数型生成函数 EGF（$\mathtt{E}$xponential $\mathtt{G}$enerating $\mathtt{F}$unction）

链接。

Part 3 生成函数变换

链接。

Part 4 一些练习

4.1 有标号无向简单连通图计数

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

设 $f_i$ 为 $i$ 个点的有标号无向简单连通图的数量， $g_i$ 为 $i$ 个点的有标号无向简单图的数量，$F(x)$、$G(x)$ 为这两个数列的 EGF，那么有：

$G(x)=\exp(F(x))$

因为所有无向简单图都可以被分成若干互不区分的连通块。

$f_i$ 很好求，有 $f_i=2^{\binom{i}{2}}$，那么由于有 $\ln(G(x))=F(x)$ 所以直接上多项式 $\ln$ 即可。

4.2 有标号二分图计数

P7364 有标号二分图计数

设 $f_i$ 为 $i$ 个点的有标号二分图数量， $g_i$ 为 $i$ 个点的有标号连通二分图，$F(x)$、$G(x)$ 为这两个数列的 EGF，那么有：

$F(x)=\exp(G(x))$

设 $h_i$ 为 $i$ 个点的有标号黑白染色图数量，$H(x)$ 为它的 EGF，显然有：

$h_i=\sum\limits_{j=0}^i \binom{i}{j}2^{j(i-j)}$

容易发现，一个有标号连通二分图只有两种染色方案，那么有：

$H(x)=\exp(2G(x))\\$

由于 $F(x)=\exp(G(x))$，所以 $F(x)=\sqrt{H(x)}$。注意到 $xy=\binom{x+y}{2}-\binom{x}{2}-\binom{y}{2}$ 所以 $H(x)$ 可以卷积求，多项式开根是 $O(n\log n)$ 的，那么总的时间复杂度为 $O(n\log n)$。

4.3 有标号毛毛虫计数

毛毛虫：一种特殊的树，满足存在一条路径，使得任何一个点到路径的距离不超过 $1$。

考虑一节一节”组装“毛毛虫，显然单独一节毛毛虫是一个菊花，其 EGF 为 $G(x)=\sum\limits_{i=1}^\infin i\frac{x^i}{i!}$

但是头和尾要特殊考虑，因为端点节只有一个点时会被端点前面那一节连出来很多点的情况算上。

那么不妨强制钦定端点节至少由两个点组成，那么端点节的 EGF 为 $B(x)=\sum\limits_{i=2}^\infin i\frac{x^i}{i!}$。

那么答案的 EGF 即为：

$\begin{aligned} F(x)&=B(x)^2\frac{1}{2}\sum\limits_{i=0}^{\infin}A^i(x)\\ &=B(x)^2\frac{1}{2}\sum\limits_{i=0}^{\infin}A^i(x)\\ &=\frac{B(x)^2}{2(1-A(x))}\\ \end{aligned}$

注意菊花和 $n\le 2$ 的情况要特判。

4.4 有标号 DAG 计数

DAG：有向无环图。

P6295 有标号 DAG 计数

考虑不断加入入度为 $0$ 的点集，设 $f_n$ 为 $n$ 个点的 DAG 个数，那么有：

$f_n=\sum\limits_{i=1}^{n}\binom{n}{i}2^{i(n-i)}f_{n-i}$

但是这样 $G=\{1\to 3,2\to 3\}$ 会被算重，发现一个点集 $S$ 的所有子集 $T\subseteq S$ 都会把 $S$ 算一次，那么根据：

$(1-1)^n=\sum\limits_{i=0}^n (-1)^i\binom{n}{i}=[n=0]\\ \sum\limits_{i=1}^n (-1)^{i-1}\binom{n}{i}=[n\not=0]\\$

所以有容斥：

$f_n=\sum\limits_{i=1}^{n}(-1)^{i-1}\binom{n}{i}2^{i(n-i)}f_{n-i}$

由于 $xy=\binom{x+y}{2}-\binom{x}{2}-\binom{y}{2}$，所以这个东西可以直接分治 NTT。

考虑设 $F(x)=\sum\limits_{i=0}^\infin \frac{f_i}{i!2^{\binom{i}{2}}}x^i$，$G(x)=\sum\limits_{i=1}^\infin\frac{(-1)^{i-1}}{i!2^{\binom{i}{2}}}x^i$，那么有：

$\begin{aligned} F(x)&\equiv F(x)G(x)+1\pmod{x^n}\\ F(x)&\equiv \frac{1}{1-G(x)}\pmod{x^n} \end{aligned}$

那么求逆就行了，优化掉了一个 $\log$。

但是洛谷上的题要求图必须弱联通，所以需要再 $\ln$ 一下。