最近在翻看伯克利的组合数学课, 恰巧看到了这个. 当时对Prufer的认知, 仅限于他能压缩一个标号树(labeled tree), 后来看到Prufer证明Cayley公式: The number of labeled tree with n nodes is n^(n-2). 感觉这个东西还稍微有点用, lol. 要知道什么是Prufer Code, 首先要了接什么是labeled tree. 标号树就是一棵树, 把每个node从1开始标号. 因为是组合数学, 所以问的是, 对于标号n的树, 有几种可能的情况, 这个是Cayley公式. Prufer用Prufer Code证明了这个公式,当然这不是第一次证明. Prufer Code很好理解, 每次拿出编号最小的node, 然后把它的邻居放到序列里, 直到剩下两个点. 逆Prufer Code也好写, 先列1~n个数, 然后拿出(不放回)没有在序列中的最小的数, 和序列首项连起来, 然后删除序列首项, 直到最后剩下两个点, 然后把这2个顶点连起来. Prufer Code最大的应用就是它的唯一性, 即: 唯一的code对唯一的labeled tree. 这也是它被发明出来证明Cayley公式的原因. 所以任意给一个正整数序列, 都能对上一棵树… 其他应用…我还真是不知道…