Codeforces 1109D: generalizations of Cayley's formula证明

做这题的时候发现题解里有提到 $generalizationsofCayle{y}^{\prime }sformula$generalizations of Cayley′s formula的，当场懵逼，Wikipedia里也就带到了一下，没有解释怎么来的，然后下面贴了篇论文。

大概就是 $n$n个点 $k$k个联通块的森林， 1,2,⋯,k属于不同的联通块，这样不同的方案数共有 $k\cdot n^{n-k-1}$k⋅nn−k−1种。

我自己用 $Pr\ddot{u}fer$Pru¨fer序列脑补了半天没搞懂怎么来的，始终觉得感性理解是 $n^{n-k}$nn−k，然后就去看了下那个证明。

用 $F(n,k)$F(n,k)表示那个方案数（ $n,k$n,k与前面意义相同），我们要证明
F(n,k)=k⋅nn−k−1(1)
证明基于下面这个公式，若 $n\>1$n>1且 $1\le k\le n$1≤k≤n则
F(n,k)=j=0∑n−k​(jn−k​)F(n−1,k+j−1)(2)
其中 $F(1,1)=1,F(n,0)=0(n\ge 1)$F(1,1)=1,F(n,0)=0(n≥1)
要证明上面的递推式，考虑一个 $n$n个点 $k$k个联通块， 1,2,⋯,k属于不同的联通块的森林，在这个森林中，一号节点可能和 {k+1,k+2,⋯,n}的任何子集相连，假设连了 $j$j个点，那么方案数就是 $\left(\frac{n-k}{j}\right)$(jn−k​)，然后删掉一号点，此时有 $n-1$n−1个点， $k+j-1$k+j−1个联通块，我们枚举 $j$j，就得到了上面的式子。

再用一下数学归纳法就可以把(2)式变成(1)式了
当 $n=1$n=1时，两式显然相等
当 $n\>1$n>1时，若 $F(n-1,i)=i\cdot (n-1{)}^{n-i-2}$F(n−1,i)=i⋅(n−1)n−i−2，则由(2)可得
F(n,i)=j=0∑n−i​(jn−i​)(i+j−1)(n−1)n−i−j−1=i⋅nn−i−1(3)
用一下二项式定理就行。

博主有话说：不得不承认这篇博文是烂尾，毕竟还不是很懂二项式定理QAQ，但感觉这个证明还挺精巧的。