首先是 Martrix67 的博文：http://www.matrix67.com/blog/archives/682
然后是morejarphone同学的博文：http://blog.csdn.net/morejarphone/article/details/50677172
因为是偶然翻了他的这篇博文，然后就秒会了。
一棵n个节点的无根树唯一地对应了一个长度为n-2的数列，数列中的每个数都在1到n的范围内。
上面这句话比较重要。通过上面的定理，
1）我们可以直接推出n个点的无向完全图的生成树的计数：n^(n-2) 即n个点的有标号无根树的计数。
2）一个有趣的推广是，n个节点的度依次为D1, D2, …, Dn的无根树共有 (n-2)! / [ (D1-1)!(D2-1)!..(Dn-1)! ] 个，因为此时Prüfer编码中的数字i恰好出现Di-1次。
即 n种元素，共n-2个，其中第i种元素有Di-1个，求排列数。
3）n个节点的度依次为D1, D2, …, Dn，令有m个节点度数未知，求有多少种生成树？(BZOJ1005 明明的烦恼)
令每个已知度数的节点的度数为di，有n个节点，m个节点未知度数，left=(n-2)-(d1-1)-(d2-1)-...-(dk-1)
已知度数的节点可能的组合方式如下
(n-2)!/(d1-1)!/(d2-1)!/.../(dk-1)!/left!
剩余left个位置由未知度数的节点随意填补，方案数为m^left
于是最后有
ans=(n-2)!/(d1-1)!/(d2-1)!/.../(dk-1)!/left! * m^left
待填之坑：无标号无根树、有标号有根树、无标号有根树的计数。
参见论文 华中师大一附中 赵爽《树的计数》、南京师范大学附属中学 顾昱洲《Graphical Enumeration》
n个点的 有标号有根树的计数：n^(n-2)*n = n^(n-1)
n个点的 无标号有根树的计数：
n个点的 无标号无根树的计数：a为 n个点的 无标号有根树的计数。
待填之坑：度数有限制时的计数。如烷烃的计数，每个点的度数最大为4。