考虑共有(k)个连通块，第(i)个联通块的大小为 (s_i) ，在最终生成的树的度数为 (d_i) 的方案数。
对应到prufer序列上就是
[{k-2choose d_1-1,d_2-1cdots 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-2choose 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}{{tchoose 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))的方案就有
[tchoose n_1,n_2,cdots,n_t
]
种，每种权值为 (prod x_i^{n_i})。
由于(sum s_i=n)于是原式即可化为
[n^{k-2}prod s_i
]