Cayley 树计数公式

Prüfer 编码之所以把树化为独立序列，是因为反复删除当前最小叶子时，只需记录它连接到谁；被删除叶子的身份可由剩余度数自动恢复。长度固定为 $n-2$，每个位置都可取 $[n]$ 中任一标号，于是复杂的无环连通约束全部被吸收到解码过程里。公式中的指数 $n-2$ 因此来自编码长度，而不是维数类的形式类比。

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

标号树边集 $\{\{1,4\},\{2,4\},\{3,4\}\}$ 的 Prüfer 序列为 $(4,4)$：依次删去最小叶子 $1,2$，都记录邻点 $4$。反向解码 $(4,4)$ 时，标号 $1,2$ 未出现，依序接到 $4$，最后连接剩余的 $3,4$。对 $n=4$，共有 $4^2=16$ 棵标号树；其中星形树的不同中心已被视为不同对象。

Prüfer 编码公理库Prüfer 编码Prüfer code · Prüfer sequence把含 $n$ 个标号顶点的树双射编码为长度 $n-2$ 的顶点序列。给出与长度 $n-2$ 的标号序列公理库序列Sequence以自然数为定义域的函数。之间的双射，从而证明完全图 $K_n$ 的生成树数。编码中标号 $v$ 出现次数等于 $\mathrm{deg}(v)-1$，还可进一步计数给定度数序列的树；与生成树公理库生成树Spanning tree包含原图全部顶点且自身为树的子图。和矩阵树定理结合后，Cayley 公式成为一般图树计数的基准。