Cayley 定理

结论  节点个数为\(n\)的无根标号树的个数为\(n^{n-2}\)。

这个结论在很多计数类题目中出现，要证明它首先需要了解 Prufer 序列的相关内容。接下来给出证明。

证明  每一棵树都可以转换为一个 Prufer 序列。根据定义，每一个节点在 Prufer 序列中出现的次数等于该节点度数减一，即\(d_i – 1\)。整个 Prufer 序列的长度为 \(\sum_i d_i – 1 = 2(n -1) – n = n – 2\)。无根树的形态可以与 Prufer 序列一一对应，所以无根树的个数也等于 Prufer 序列的个数。故个数为 \(n^{n-2}\)。

Cayley 在 1889 年证明了这个定理，Cayley 在证明之后提出了一个新的问题：

问\(n\)个节点组成\(s\)个树的森林有多少种？

Cayley 之后便没能找到这个问题的解了。接下来我们引入「扩展 Cayley 定理」。

扩展 Cayley 定理

Cayley 提出了这个问题的可能解：

\[ F(n, s) = sn^{n – s – 1} \]

然而，Cayley 便将这个问题抛在一边，临终前并没能完成证明。上个世纪很多计算机科学家运用了很多方法来证明，我参考了 LAJOS TAKACS 的 On Cayley’s Formula for Counting Forests 这一文章。现在我来进行转述。

证明   首先有递归式：

\[ F(n, s) = \sum_{j = 0}^{n – s} {n – s \choose j} F(n – 1, s + j – 1) \]

我们先来证明这个递归式。假设我们所在的点为节点 1，枚举\(j\)为节点 1 的儿子个数。对于每一个\(j\)有\(n – s \choose j\)种方式在剩余的点中进行选择，然后递归下去：删除自身节点，对于\(j\)个儿子的方案数，我们直接加入递归子问题中，也就是\(F(n – 1, s + j – 1)\)。将 Cayley 的猜想式子带入即可证明。