这个结论在很多计数类题目中出现,要证明它首先需要了解 Prufer 序列的相关内容.接下来给出证明.
Cayley 在 1889 年证明了这个定理,Cayley 在证明之后提出了一个新的问题:
Cayley 之后便没能找到这个问题的解了.接下来我们引入"扩展 Cayley 定理".
然而,Cayley 便将这个问题抛在一边,临终前并没能完成证明.上个世纪很多计算机科学家运用了很多方法来证明,我参考了 LAJOS TAKACS 的 On Cayley's Formula for Counting Forests 这一文章.现在我来进行转述.
证明 首先有递归式: