四种树的计数

imily's notebook

2021-05-05

prufer, 生成函数

prufer、生成函数都是数树的利器。

prufer 真的超好用！！有标号树计数，不管怎么变，只要考虑在 prufer 序列中的出现情况就都能解决。

有标号无根树

Cayley 公式：完全图生成树个数为 $n^{n - 2}$

广义 Cayley 公式：$n$ 个有标号节点形成 $k$ 棵树，使得给定 $k$ 个点两两不在同一棵树中的方案数为 $k n^{n - k - 1}$（实际上没怎么懂这个东西，现推推也挺快的（CF1109D））

有标号有根树

$n^{n - 1}$

无标号有根树

设 $f_i$ 表示大小为 $i$ 的树的方案数，其生成函数为 $F(z) = \sum\limits_{i \geq 0} f_i z^i$，则

$$F(z) = z \prod\limits_{i \geq 0} (1 - z^i)^{-f_i}$$

取对数

$$\ln{F(z)} = \ln{z} + \sum\limits_{i \geq 0} \ln((1 - z^i)^{-f_i})$$

$$= \ln{z} - \sum\limits_{i \geq 0} f_i \ln(1 - z^i)$$

求导

$$\frac{F’(z)}{F(z)} = \frac{1}{z} + \sum\limits_{i \geq 0} f_i \frac{i z^{i - 1}}{1 - z^i}$$

化简

$$z F’(z) = F(z) + F(z) \sum\limits_{i \geq 0} f_i i \frac{z^i}{1 - z^i}$$

只看第 $n$ 项系数

$$n f_n = f_n + \sum\limits_{i = 1}^{n - 1} f_i \sum\limits_j [j \mid n - i] f_j j$$

$$f_n = \frac{1}{n - 1}( \sum\limits_{i = 1}^{n - 1} f_i \sum\limits_j [j \mid n - i] f_j j )$$

可以用分治 NTT 解决。~~假装我会吧，现在实在没心情写~~

无标号无根树

设 $g_i$ 表示无根树的方案，$f_i$ 同上。考虑无根树可以用重心表示，所以把不是重心的答案都减去。

$$h_n = f_n - \sum\limits_{i = 1}^{n / 2} f_i f_{n - i}$$

注意当 $n$ 为偶数时要特判，加上 $f_{n / 2}^2 - \binom{f_{n / 2}}{2}$。

upd: 再更点 prufer 内容。

$n$ 个点的有标号无向图有 $k$ 个连通块，每个连通块大小为 $a_i$，要求添加 $k - 1$ 条边使其连通，方案数为 $n^{k - 2} \prod a_i$。证明就多元二项式定理 ~~（多项式定理）~~ 搞一搞。

雅礼集训-共

树是个按深度奇偶分类的二分图。

那么相当于数左部点个数为 $k$ 的二分图个数。

组合数 + prufer（考虑最终 prufer 序列中两边点出现的次数）：$ans = \binom{n - 1}{k - 1} * k^{n - k - 1} * (n - k)^{k - 1}$

$Code$

$CF1109D$

枚举 $a$、$b$ 距离。生成树个数可以广义 Cayley 直接算，也可以推柿子。还是推一下：

当前链大小为 $i$。枚举链中元素在 prufer 序列中出现的次数 $k$。

$tree num = \sum\limits_{k = 0}^{n - i - 1} i^{k + 1} \binom{n - i - 1}{k} (n - i)^{n - i - 1 - k} = i * n^{n - i - 1}$

$Code$

清训-生成树计数

度数相关，考虑 prufer。

$c_i$ 表示 $i$ 在 prufer 序列中出现的次数。枚举序列长啥样，第 $i$ 块某次出现是其中哪个点连出去了。

$ans = (n - 2)! \prod a_i \prod\limits_{\sum c_i = n - 2} \frac{(c_i + 1^m a_i^{c_i})}{c_i!} ( \sum_i (c_i + 1)^m )$

$= (n - 2)! \prod a_i \sum\limits_{\sum c_i = n - 2} \frac{(c_i + 1)^{2m} a_i^{c_i}}{c_i!} \prod\limits_{j \neq i} \frac{(c_j + 1)^m a_j^{c_j}}{c_j!}$

EGF 出来了。

设 $A(x) = \sum_i \frac{(i + 1)^{2m}}{i!} x_i$, $B(x) = \sum_i \frac{(i + 1)^m}{i!} x_i$，
$ans = (n - 2)! \prod a_i [x^{n - 2}] \sum_i \frac{A(a_ix)}{B(a_ix)} \exp( \sum_j \ln( B(a_jx) ) )$

$\frac{A(x)}{B(x)}$ 和 $\ln(B(x))$ 是好求的，怎么带 $a$ 进去？

以 $\ln(B(a_jx))$ 为例，设 $B’ = \ln B$，$\sum_j B’(a_jx) = \sum_i B’_i \sum_j a_j^i$

$\sum_j a_j^i = [x^i] \sum_j \frac{1}{1 - a_jx}$，通分 + 分治求这个即可。

$Code$