形式陈述

对 $n\ge 2$，完全图 $K_n$ 的生成树数，即顶点标号为 $1,\dots ,n$ 的树数，为

$$n^{n-2}.$$

Prüfer 编码给出标号树与长度 $n-2$ 的 $[n]$-值序列之间的双射，因此树数等于序列数。

直觉

复杂的分枝结构经双射变为每个位置独立选择一个标号的普通序列。

例子与边界

$n=3$ 时共有 $3$ 棵标号树。公式计数标号树而非树的同构类型；无标号树数量没有同样简单的闭式。

推论与应用

它连接生成树计数、随机树、矩阵树定理和组合双射。

参考资料

• Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science (2018/2024), Cayley formula.
• Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd ed. (2011), Prüfer enumeration.