0%

烷烃计数

任何点的度数小于等于 $4$ 的无标号无根树个数。

烷基计数

我们先来数烷基。(任何节点均最多只有三个儿子的无标号有根树)

设 $f_i$ 是 $i$ 个点的烷基个数。有标号情况下的 DP 非常显然:

Burnside引理 可以得到无标号情况下的 DP

写成 OGF 就是

牛迭即可。

烷烃计数

还是考虑重心的套路。

有一个结论:一棵树点等价类的数量 $p$(点的等价可以理解为将其定为根后整棵树的等价)减边等价类的数量 $q$ 加上 $[\text{其重心的数量为 }2]$(记为 $s$)等于 $1$。

容易发现所有不同构无根树的 $p$ 之和其实就是有根树的数量。类似烷基的式子,不过儿子数为 4。

所有 $q$ 之和就是两个烷基拼起来。注意特判 $n=0$。

$s$ 也很显然:有两个重心的无根树必然是两个大小相等的烷基拼起来。

于是烷烃数量即为