Cayley 定理 & 扩展 Cayley 定理

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 的猜想式子带入即可证明。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注