\(Prufer\)序列
在一棵\(n\)个点带标号无根树里，我们定义这棵树的\(Prufer\)序列为执行以下操作后得到的序列
1.若当前树中只剩下两个节点，退出，否则执行\(2\)
2.令\(u\)为树中编号最小的叶子节点，记\(v\)为唯一与\(u\)有边相连的节点，把\(u\)删去，并将\(v\)加入到序列的末尾，重复\(1\)
显然，得到的\(Prufer\)序列是一个长度为\(n-2\)的序列
易证每一棵\(n\)个节点的有标号无根树都唯一对应一个长度为\(n-2\)的\(Prufer\)序列
无根树对应序列很容易证明，接下来我们要证明的是序列唯一对应无根树。我们只要知道如何根据序列求对应的无根树，并且保证求出的无根树唯一即可
根据序列求无根树，就是重复下列过程
令
1.令\(A=\{1,2,3,...,n\}\)，不断重复\(2\)直到\(Prufer\)序列为空
2.找到\(A\)中最小的不在\(Prufer\)序列中的元素，将其与\(Prufer\)序列首元素连边，同时删除这个点和\(Prufer\)序列首元素
3.此时\(A\)中还剩下两个点，将它们连边即可
不难看出，如果一个点在树中度数为\(deg_i\)，那么它在\(Prufer\)序列中的出现次数为\(deg_i-1\)
\(Cayley's\ Formula\)
因为长度为\(n-2\)，每个元素取值范围为\([1,n]\)的序列个数为\(n^{n-2}\)，根据无根树与\(Prufer\)序列的一一对应关系，有
\(n\)个点带标号无根树的个数为\(n^{n-2}\)
另外还有一个拓展
设树中点\(i\)的度数为\(d_i\)，那么对应的无根树数量为\({(n-2)!\over \prod_{i=1}^n d_i}\)
\(Generalized\ Cayley's\ Formula\)
设\(f(n,m)\)为\(n\)个点构成\(m\)棵树，且\(1,2,3...,m\)全都不在同一棵树中，的方案数，有标号，无根
先给结论
\[f(n,m)=mn^{n-m-1}\]
当\(m=1\)时有\(f(n,1)=n^{n-2}\)，即为\(Cayley's\ Formula\)
证明的话，我们采用归纳法
首先对于边界条件，有\(f(1,1)=1,f(n,0)=0\)
我们假设对于所有\(k<n\)，\(f(k,m)=mk^{k-m-1}\)恒成立，接下来我们要证明\(f(n,m)=mn^{n-m-1}\)
为了方便起见，我们
我们枚举\(1\)号点的度数\(i\)，以及与\(1\)相连的这\(i\)个点，那么去掉\(1\)号点之后，会留下\(n-1\)个点和\(m+i-1\)棵树，于是有
\[f(n,m)=\sum_{i=0}^{n-m}{n-m\choose i}f(n-1,m+i-1)\]
根据归纳，因为对于所有\(k<n\)，\(f(k,m)=mk^{k-m-1}\)恒成立，所以
\[ \begin{aligned} f(n,m) &=\sum_{i=0}^{n-m}{n-m\choose i}f(n-1,m+i-1)\\ &=\sum_{i=0}^{n-m}{n-m\choose i}(m+i-1)(n-1)^{n-m-i-1}\\ \end{aligned} \]
我们把\(i\)变成\(n-m-i\)，柿子变成
\[ \begin{aligned} f(n,m) &=\sum_{i=0}^{n-m}{n-m\choose i}(n-i-1)(n-1)^{i-1}\\ &=\sum_{i=0}^{n-m}{n-m\choose i}(n-1)(n-1)^{i-1}-\sum_{i=0}^{n-m}{n-m\choose i}i(n-1)^{i-1}\\ &=\sum_{i=0}^{n-m}{n-m\choose i}(n-1)^i-\sum_{i=0}^{n-m}{n-m\choose i}i(n-1)^{i-1}\\ \end{aligned} \]
前面那个东西，根据二项式定理，为\(n^{n-m}\)
后面那个东西，我们把\({n-m\choose i}i\)化为\({n-m-1\choose i-1}(n-m)\)
\[ \begin{aligned} \sum_{i=0}^{n-m}{n-m\choose i}i(n-1)^{i-1} &=\sum_{i=0}^{n-m}{n-m-1\choose i-1}(n-m)(n-1)^{i-1}\\ &=(n-m)\sum_{i=0}^{n-m-1}{n-m-1\choose i}(n-1)^i\\ &=(n-m)n^{n-m-1} \end{aligned} \]
代入柿子即可
定理拓展
\(n\)个带权的点，边的权值为连接两点点权之积，树的权值为所有边权值之积，求所有树的权值之和
令\(i\)的度数为\(d_i\)，权值为\(val_i\)，则一棵树的权值即为
\[\prod_{i=1}^n{val_i}^{d_i}\]
考虑\(Prufer\)序列，每个点恰出现\(d_i-1\)次，那么根据乘法分配律，答案为
\[\left(\prod_{i=1}^n{val_i}\right)\left(\sum_{i=1}^nval_i\right)^{n-2}\]
这个东西似乎包含了上面的所有定理。当所有点权值为\(1\)时，就是\(Cayley's\ Formula\)。当把\(1\)到\(m\)缩成一个权值为\(m\)的点时，就是\(Generalized\ Cayley's\ Formula\)
参考资料