冬令营的时候完全不会生成函数，听这块的时候全程掉线。。现在洛谷有了这两个模板，于是来总结一下自己的理解。

参考资料：WC2019 课件《生成函数，多项式算法与图的计数》

本文中图的计数均指有标号图的计数。

前置知识

无向连通图计数

设 f_n 表示 n 个点的简单连通图个数，也就是我们要求的东西。

我们令 g_n 表示 n 个点的简单无向图（不一定连通）个数。考虑每条边选/不选，容易得到 g_n=2^{\binom{n}{2}} .

设 F(x),G(x) 分别为 \left\{f_n\right\},\left\{g_n\right\} 的指数生成函数。考虑把一个不连通的图划分为若干个连通块，那么这些块之间没有联系，且每个块内部的生成函数是 F(x) . 这个模型可以视为将 n 个元素划分为任意多个非空子集，每个大小为 k 子集内部有 f_k 种染色方案，即 G(x)=\exp\;F(x) . 反过来要求 F(x) ，那么有 F(x)=\ln\;G(x) ，套一下多项式板子即可。

（扩展）拉格朗日反演

复合逆

若两个函数 F(x), G(x) 满足 F(G(x))=x ，则称 F 与 G 互为复合逆。此时有 G(F(x))=x 且 F 和 G 的常数项均为 0 .

拉格朗日反演是在 F(x),G(x) 为多项式且已知 G 的情况下求 F 的某一项系数的一种方法。有关系式：

[x^n]F(x)=\frac{1}{n}[x^{-1}]\frac{1}{G^n(x)}

要用 -1 次幂就很难受，乘个 x^n 就可以变成：

[x^n]F(x)=\frac{1}{n}[x^{n-1}]\left(\frac{x}{G(x)}\right)^n

然后拉格朗日反演还有它的扩展形式（以下两个算法都会应用到它）：

[x^n]H[F(x)]=\frac{1}{n}H'(x)\left(\frac{x}{G(x)}\right)^n

边双连通图计数

这个好像比较简单，就从这个说起吧。

设 b_n 表示 n 个点的有根边双连通图个数，d_n 表示 n 个点的有根连通图个数，对应的指数生成函数分别为 B(x) 和 D(x) （实际上有根和无根的区别就是乘了个 n）。

考虑一个连通图。它长成这个样子：

其中 1 号点为根节点。我们把一个边双缩成一个方点： （图中节点对应的原图节点编号的区间）

设根节点所在的边双叫做 S ，其中有 n 个点，则它所对应的指数 EGF 为 \frac{b_nx^n}{n!} . 然后这个边双中会引出几条到别的连通子图里的边。考虑其中一个连通子图，它内部方案的生成函数为 D(x) 。此外，它的根节点还会通过这条边连向 S 中的任意一个节点，所以这一部分的生成函数就变成了 nD(x) . 我们把连向 S 中同一点的连通子图视为一类，则一类中的连通子图是可以任意交换顺序的。那么所有外挂连通子图的生成函数就是 \exp(nD(x)) . 枚举 S 的大小并求和得

D(x)=\sum_{n\geq 1}\frac{b_nx^n\exp(nD(x))}{n!}=B(x\exp D(x)) .