考虑共有\(k\)个连通块，第\(i\)个联通块的大小为 \(s_i\) ，在最终生成的树的度数为 \(d_i\) 的方案数。

对应到prufer序列上就是

\[{k-2\choose d_1-1,d_2-1\cdots d_k-1}\prod {{s_i}^{d_i}}=\frac{(k-2)!}{\prod (d_i-1)!}\prod {{s_i}^{d_i}} \]

看到这个\(d_i-1\)的形式似乎不是很优美，设\(f_i=d_i-1\)，即

\[{k-2\choose e_1,e_2,\cdots ,e_k}\prod{s_i^{e_i+1}} \]

这是个多项式定理的形式，多项式定理即为项数多于 \(1\) 的情况下

\[(x_1+x_2+\cdots+x_t)^m=\sum_{\sum n_i=t}{{t\choose n_1,n_2,\cdots,n_t}}\prod x_i^{n_i} \]

\(n_i\) 为 \(x_i\) 这项的系数，一个比较简单的证明：从 \(m\) 项中选择 \(n\) 个数，那么组合为 \((n_1,n_2,\cdots,n_t)\)的方案就有

\[t\choose n_1,n_2,\cdots,n_t \]

种，每种权值为 \(\prod x_i^{n_i}\)。

由于\(\sum s_i=n\)于是原式即可化为

\[n^{k-2}\prod s_i \]