Prüfer 序列
因为 ü 太难打了，所以下文的 Prüfer 将用 Prufer 代替。
Prufer 序列是利用一个长度为 \(n - 2\) 的序列唯一描述一颗有标号树的序列。
换句话说 Prufer 序列和树是双射，这就使得它在计数问题当中及其常用，这里我们只考虑节点数 \(\ge 2\) 的树。
构造ψ(｀∇´)ψ
构造过程大概是这样的：
- 每次选择一个编号最小的叶子节点，删除，并记录下它最后连接节点的编号。
- 重复 \(n - 2\) 次。
比较懒不想画图就用 OI-wiki 的例子了：
可以注意到几个性质：
- 如果 \(i\) 在 Prufer 序列中出现了 \(k\) 次，那么原树中 \(i\) 的度数是 \(k + 1\)。
- 最后原树剩下的节点一定有一个是编号最大的节点 \(n\)。
Cayley 公式ψ(｀∇´)ψ
完全图 \(K_n\) 有 \(n^{n - 2}\) 棵生成树。
这个用 Prufer 可以证明，但是我这里先不提，只提一个结论。
一个结论：对于给定的度数序列 \(\{d\} \text{s.t. } \sum\limits_{i = 1}^{n}d_i = 2n - 2\)，构造 Prufer 序列的方案数是：
\[
\dbinom{n - 2}{d_1 - 1, d_2 - 1, \dots, d_n - 1} = \dfrac{(n - 2)!}{(d_1 - 1)!(d_2 - 1)! \dots (d_n - 1)!}
\]
之前有个计数题用到了但是我忘记是啥了，有时间来补一下。
最后更新:
July 14, 2023