用于解决带标号的生成树计数问题，一般用于计数问题。
建立 Prüfer 序列
重复下列操作 \(n-2\) 次，得到长度为 \(n-2\) 的 Prüfer 序列。
-
取出编号最小的叶子节点 \(x\)，将与 \(x\) 相连的节点加入 Prüfer 序列中。
-
将 \(x\) 和与 \(x\) 相连的边删去。
明显的，每个点在 Prüfer 序列里出现了 \(d_x-1\) 次（\(d_x\) 表示点 \(x\) 的度数，下同）。
Prüfer 序列重建树
因为每个点在 Prüfer 序列里出现了 \(d_x-1\) 次，所以我们可以得知每个点的度数（存在数列 \(a\) 中）。
重复下列操作 \(n-2\) 次：
- 选择点的度数为 \(1\) 的编号最小的点 \(x\)，将 \(x\) 和 Prüfer 序列的第一个数 \(y\) 连接。
- \(d_x\gets d_x-1\)，\(d_y\gets d_y-1\)，将 Prüfer 序列的第一个数删去。
Prüfer 序列的性质以及定理
性质
一棵树和其 Prüfer 序列形成双射。
在构建 Prüfer 序列中，剩下的两个点其中一个必定为 \(n\)。
每个点在 Prüfer 序列里出现了 \(d_x-1\) 次。
定理
有标号无向完全图的不同生成树数
若该有标号无向完全图有 \(n\) 个点则该无向完全图的不同生成树数为 \(n^{n-2}\)。
Prüfer 序列的值域为 \([1,n]\)，长度为 \(n-2\)，所以一共有 \(n^{n-2}\) 个不同的 Prüfer 序列，也就是有 \(n^{n-2}\) 个不同的生成树。
\(n\) 个点的有根树计数
不同的有根树个数为 \(n^{n-1}\)。
有根树个数等于无根树个数乘以 \(n\)，即 \(n^{n-1}\)。
\(n\) 个点的无根树计数（点的度数已知）
设 \(0!=1\)，点 \(x\) 的度数为 \(d_x\)。则 Prüfer 序列中 \(x\) 出现 \(d_x-1\) 次。也就是可重元素的全排列个数问题。即 \(\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}\)。
标签：Pr,度数,个点,根树,fer,序列 From： https://www.cnblogs.com/dadidididi/p/17658063.html