图的计数

无标号计数

1、二叉树

设OGF为$H(x)=\sum_{i=0}^{\infty}h_ix^i$。
任意一棵大小为$n(n\ge 1)$二叉树去掉根，可以得到两棵大小之和为$n-1$的二叉树。因此$h_n=\sum_{i=0}^{n-1}h_ih_{n-1-i}(n\ge 1)$。

根据递推关系可列出方程$xH(x)^2-H(x)+1=0$。
解得$H(x)=\frac{1-\sqrt{1-4x}}{2x}$。
求得$h_n=\frac{\binom{2n}{n}}{n+1}$。

*预备知识：Euler变换

Euler变换在无标号计数中的组合意义相当于有标号计数中的exp，即阶数之和为$n$的结构的任意组合。

设$F(x)=\sum_{i=0}^{\infty}f_ix^i$。
定义$\mathcal{E}(F(x))=\prod_{i=0}^\infty \frac{1}{(1-x^i)^{f_i}}$。
上式可化为$\mathcal{E}(F(x))=\exp(\sum_{i=1}^\infty\frac{F(x^i)}{i})$。

2、有根树

设OGF为$F(x)=\sum_{i=0}^\infty f_ix^i$。
任意一棵大小为$n(n\ge 1)$的有根树去掉根，可以得到若干棵大小之和为$n-1$的有根树。因此$F(x)=x\mathcal{E}(F(x))$。

2*、无根树

设有根树的OGF为$F(x)=\sum_{i=0}^\infty f_ix^i$，无根树的OGF为$H(x)=\sum_{i=0}^\infty h_ix^i$。
要统计无根树，只需统计以重心为根的有根树。根据重心的定义一个点是重心当且仅当它的每棵子树大小不超过$[\frac{n}{2}]$。
因此，一棵树有2个重心当且仅当重心最大子树的大小恰好是$\frac{n}{2}$，否则只有1个重心。当树有两个重心时，也要把重心重复计算的情况给减去。
因此，$h_n=\begin{cases}f_n-\sum_{k=\frac{n+1}{2}}^{n-1}f_kf_{n-k}&n为奇数\\f_n-\sum_{k=\frac{n}{2}+1}^{n-1}f_kf_{n-k}-\binom{f_{\frac{n}{2}}}{2}&n为偶数\end{cases}$。
即$H(x)=F(x)-\frac{1}{2}F(x)^2+F(x^2)$。

有标号计数

1、无根树

由Prufer序列和无根树的一一对应关系，得答案$n^{n-2}$。

1*、有根树

答案$n^{n-1}$。

2、无向连通图

设$n$阶有标号无向连通图有$f_n$种。
设$F(x)=\sum_{i=0}^\infty \frac{f_i}{i!}x^i$。
则$\exp F(x)=\sum_{i=0}^\infty\frac{2^\binom{i}{2}}{i!}x^i$。
即$F(x)=\ln\sum_{i=0}^\infty\frac{2^\binom{i}{2}}{i!}x^i$

3、点双连通图

设无向连通图的EGF为$F(x)$，有根无向连通图的EGF为$D(x)$，则$[x^n]F(x)=n[x^n]D(x)$。
设点双连通图的EGF为$B(x)$。
任意一个大小为$n$的有根无向连通图去掉根都可以得到若干个大小之和为$n-1$的连通块。对每个连通块，考虑根所在的点双连通分量，每个点作为根，都可以向外连出一个有根无向连通图。
因此一个连通块的EGF为$\sum_{i=1}^\infty \frac{b_{i+1}D^i(x)}{i!}=B'(D(x))$。
因此$D(x)=\exp B'(D(x))$。

4、边双连通图

设有根无向连通图的EGF为$D(x)$，边双连通图的EGF为$B(x)$。
考虑根所在的边双连通分量，每个点都可以向外连接若干个有根无向连通图的根。
因此$D(x)=\sum_{i=1}^\infty \frac{b_ix^i\exp iD(x)}{i!}=B(x\exp D(x))$

5、仙人掌

设EGF为$F(x)=\sum_{i=0}^\infty \frac{f_i}{i!}x^i$。
$F=x\exp (F+\frac{1}{2}\sum_{i=2}^\infty F^i)=x\exp \frac{F(2-F)}{2(1-F)}$

6、DAG

设EGF为$F(x)=\sum_{i=0}^\infty \frac{f_i}{i!}x^i$。
$f_n=\sum_{i=1}^n(-1)^{i-1}\binom{n}{i}2^{i(n-i)}f_{n-i}$。

7、欧拉图

设EGF为$F(x)=\sum_{i=0}^\infty \frac{f_i}{i!}x^i$。每个点度数均为偶数的图的EGF为$G(x)=\sum_{i=0}^\infty \frac{g_i}{i!}x^i$。
对于任意一个$n-1$阶的图，都可以新加一个点$n$，与图中所有度数为奇数的点连边。
因此$g_n=2^\binom{n-1}{2}$。
而$G(x)=\exp F(x)$。
因此$F(x)=\ln G(x)$。