prufer序列计数的一些结论

1. \(prufer\)序列和完全图的生成树一一对应（考虑构造）

2. 完全图的生成树个数为\(n^{n - 2}\)

3. 满足第\(i\)个点的度数为\(d_i\)的生成树为\(\frac{n!}{\prod (d_i - 1) !}\)

4. 把\(m\)个联通块，第\(i\)个大小为\(a_i\)，连接起来的方案数为\(n^{m - 2} \prod a_i\)

5. \(n\)个点，形成\(k\)个森林的方案数为\(k * n^{n - k - 1}\)

原文：https://www.cnblogs.com/reverymoon/p/10398354.html