0%

有标号仙人掌计数

每条边最多仅在一个环上的有标号无向图个数。

显然有标号无根图(相当于钦定根为 $1$)的数量是对应的有标号有根图的 $\frac 1 n$,所以下面我们只讨论有根仙人掌。

枚举根的每个“儿子”,一个“儿子”可能与根以一条边相连(一棵仙人掌,$F(x)$),也有可能由一个环相连(如果环的大小为 $i$,其下方可以接上 $i-1$ 棵仙人掌,又由于环可以翻转,所以生成函数即为 $\frac {F^{i-1}(x)}2$)。

所以有:

构造函数 $A(X)=X\exp(\dfrac{-X^2+2X}{2-2X})-X$,多项式牛迭即可。