Prufer序列

Prufer序列的构造略,这里主要总结应用.

完全图 $K_n$ 有 $n^{n-2}$ 棵生成树.证明:Prufer序列值域是[1,n],有n-2个,QED.

性质

在Prufer序列中出现次数为d-1的节点的度数是d.

所以,给一个序列表示每个点的度数,可以计算出来这样的无根树一共有

$$\prod_{i=1}^n\binom{rest}{d_i-1}$$

个,rest表示每次选数剩下的位置.

图联通方案数

一个n个点m条边的带标号无向图有k个连通块.我们希望添加k-1条边使得整个图连通.求方案数.

首先是多项组合数公式:表示从

$$\binom{a}{b,c,d}=\frac{a!}{b!c!d!}$$

然后是多元二项式定理:

$$(x_1+...+x_m)^p=\sum_{c_i\ge0,\sum_{i=1}^{m}c_i=p}\binom{p}{c_1,...,c_m}\cdot\prod_{i=1}^{m}x_i^{c_i}$$

结论:

$$n^{k-2}\cdot\prod_{i=1}^{k}s_i$$