Cayley 树计数公式

树的边必须同时满足连通、无圈，看起来并不能独立选择。Prüfer 编码理路Prüfer 编码Prüfer code · Prüfer sequence把含 $n$ 个标号顶点的树双射编码为长度 $n-2$ 的顶点序列。把这些约束吸收进解码规则，转而用一串完全自由的标号描述每棵树。

双射证明的三个环节 ​

先对每棵树反复删除最小标号叶子并记录邻点，直到剩下两个顶点。每次删除一个顶点，所以记录恰有 $n-2$ 项，每项都在 $[n]$ 内。

再从任意长度 $n-2$ 的序列重建树：当前最小的未删除且不出现在剩余序列中的标号，就是下一片叶子；把它接到首项并移去首项，最后连接剩余两点。剩 $m$ 个顶点时只有 $m-2$ 个记录，总有未出现标号，因而过程不会卡住。

最后核对互逆。顶点在剩余序列中的出现次数等于当前度数减一，因此解码选中的恰是编码刚刚删去的最小叶子。逐步恢复每条边，便同时证明不同树不会撞码、每个序列都有树对应。于是由乘法原理理路乘法原理Product rule · Multiplication principle分阶段且每阶段选择数固定时，总数等于各阶段选择数之积。，$n-2$ 个位置各有 $n$ 种选择，得到 $n^{n-2}$。

单说“树能编码成这种序列”只能给出上界；还需要任意序列都可解码，才能得到精确等式。

四个顶点的两种独立核对 ​

公式给出 $T_4=4^2=16$。编码 $(4,4)$ 对应边集 $\{14,24,34\}$：依次删去叶子 $1,2$ 都记录 $4$，最后保留 $34$。

也可按形状直接计数。四点树只有星形和路径两类。星形有四种中心；路径可把四个标签排成一列，再把正向与反向视为同一条无向路径，所以有 $4!/2=12$ 棵。合计 $4+12=16$，与公式吻合。

这也说明不能把标号树数简单除以 $n!$ 来求无标号树数：星形和路径的自同构数量不同，它们各自拥有的不同标号版本也不同。此处无标号形状只有两种，而 $16/24$ 连整数都不是。

公式究竟计了什么 ​

公式没有指定根。若在每棵标号树上额外选择一个根，就有 $n\cdot n^{n-2}=n^{n-1}$ 个有根对象。若根标签预先固定，则数量仍是 $n^{n-2}$。

公式也没有给定母图的边限制。对于四圈 $C_4$，生成树只能删除其四条边中的一条，所以共有四棵，不能套用 $4^2$。$K_n$ 允许任意标签对相连，才覆盖全部标号树。

若指定每个标签的度数为 $d_i\ge 1$，并满足 $\sum _i{d}_i=2n-2$，Prüfer 编码中标签 $i$ 必须出现 $d_i-1$ 次。因此树数是多项式系数理路多项式系数Multinomial coefficient把 n 个可区分对象分入若干有标号组时的计数系数 n!/(n1!⋯nk!)。

例如度数为 $(3,1,1,1)$ 的树只有一棵，而 $(2,2,1,1)$ 对应两棵。将所有允许的度数向量相加，重新得到 Cayley 总数。

一般图的生成树理路生成树Spanning tree包含原图全部顶点且自身为树的子图。计数可用矩阵树定理；Cayley 公式提供完全图上的闭式基准。它也支持均匀随机标号树生成：均匀采样 Prüfer 序列再解码即可，均匀性由一一对应保证。