公式已证明

标号树的凯莱公式

命题陈述

对任意整数 $n \ge 1$ ， $n$ 个标号顶点 $\{1,\dots,n\}$ 上的树的个数为 $n^{n-2}$ （当 $n=1$ 时约定 $1^{-1}=1$ ）。

为什么成立?

$n$ 个顶点上的每棵标号树都可以通过反复摘除编号最小的叶节点并记录其邻居，唯一编码为由 $n-2$ 个顶点标号组成的序列（即它的普吕弗序列）；反过来， $\{1,\dots,n\}$ 中任意长度为 $n-2$ 的序列都能唯一解码为一棵树，因此这样的树共有 $n^{n-2}$ 棵。

证明思路

构造 $\{1,\dots,n\}$ 上的标号树与 $\{1,\dots,n\}^{n-2}$ 中序列之间的普吕弗双射：在 $n-2$ 步中的每一步，删去标号最小的叶节点，并将其唯一邻居的标号追加到序列末尾，最后只剩一条边。注意到每个顶点 $v$ 在普吕弗序列中恰好出现 $\deg(v)-1$ 次，因此原树的叶节点就是未出现在序列中的标号，这使得每一步都可以唯一逆转，从而建立双射。

用到此定理的主题

树

参考文献

Arthur Cayley (1889). A theorem on trees