学习笔记·多项式专题（四）

这篇文章是数数题推柿子指不着北。

例题$1$

Luogu P4841（有标号无向连通图计数）

这里先给大家讲一个普遍的结论：

假设对于某符合条件的点有标号的图的个数$\texttt{EGF}$为$F(x)$，联通的符合条件的点有标号的图的个数的$\texttt{EGF}$为$G(x)$，则

$$F(x)=e^{G(x)}$$

证明如下

枚举连通块。考虑到$f_i$已经消除了标号的影响，而$G(x)^k$却由于乘法没有消除标号的影响，所以有

$$F(x)=\sum\limits_{i=0}^{\infty}\frac{G(x)^i}{i!}=e^{G(x)}$$

至于为什么是$G(x)^k$的话，背包计数的原理。每个连通图看作是一个花费节点数的容量的物品就好了。

这对于后面的一个叫做有标号荒漠计数的题有用。

所以在这个题里面$F(x)$很好求，有

$$F(x)=\sum\limits_{i=0}^{\infty}2^{C_i^2}x^i$$

然后，$G(x)=\ln F(x)$，于是就求完了qwq。