Prufer 序列

Prufer 序列

$n$ 个点有标号无根树方案数：$n ^ {n - 2}$

考虑转化成组合意义：对于每棵有标号无根树，可以将其唯一地映射到一个长度为 $n - 2$，值域为 $[1, n]$ 的序列中。

建立 Prufer 序列

每次选择一个编号最小的叶结点并删掉他，然后在序列中记录他的父亲，如此重复 $n - 2$ 次。

$O(n)$ 实现：首先，删除一个叶结点，叶结点数量是单调不增的，只会不变或减一。我们维护一个指针 $p$，初始时指向编号最小的叶结点。执行如下操作：

• 删除 $p$ 指向的结点，并检查是否产生新的叶结点。
• 如果产生了，假设编号为 $x$。如果 $x < p$，则删掉 $x$，然后重复操作直到有 $x > p$；如果 $x > p$，则不做任何操作。
• 让 $p$ 自增，直到找到下一个没被删除的叶结点。

正确性：因为 $p$ 是目前编号最小的叶子，若 $x < p$，则 $x$ 是目前编号最小的叶结点；若 $x > p$，则在后面的操作中会删除它，所以不用操作。

以上过程说明了 Prufer 序列有两个性质：

• 构建完 Prufer 序列后原树会剩下两个结点，其中一个是编号最大的点 $n$。

  这个是因为任意剩下结点数 $> 2$ 的树，叶子数目必然 $\geq 2$，所以一定有 $< n$ 的叶子。

• 每个点的出现次数等于其儿子数，所以没出现的就是叶子结点。

Prufer 序列建树

和建立 Prufer 序列差不多。每次选择一个度数为 $1$ 的编号最小的结点，和当前枚举到的 Prufer 序列的点连起来，度数 $-1$，如果产生了新的度数为 $1$ 的点就重复操作，否则就找下一个度数为 $1$ 的点。最后我们剩下两个度数为 $1$ 的点，其中一个是 $n$，把他们连接起来即可。

应用

$n$ 个点有标号有根树：根有 $n$ 种情况，所以答案是 $n ^ {n -1}$

$n$ 个点有标号有根树森林：不妨把每个连通块连到一个新点上，那么就是 $n + 1$ 个点的树，答案为 $(n + 1) ^ {n - 1}$。

Cayley 公式

$n$ 个点的完全图有 $n^{n - 2}$ 棵生成树。

Prufer 序列证明显然。

广义 Cayley 公式

$n$ 个结点形成的有 $k$ 棵树的森林，求给定的 $k$ 个点中不存在两个点在同一棵树内的方案数。

把每个树根 $r$ 连接到一个新点 $0$ 上，形成一棵树。考虑这棵树的 Prufer 序列，长度为 $n - 1$。然后你考虑序列里一共有 $k - 1$ 个 $0$，他们的值已经确定了，序列里一定有一个数是连到 $0$ 的，其只有 $k$ 种可能性，其余的数有 $n$ 种可能性。

所以答案是 $k \times n ^ {n - k - 1}$。

给定度数的树的个数

不妨假设边都是无向的，如果给定了 $n$ 个点的度数 $d_1, \cdots, d_n$，求满足要求的树的个数。

容易发现，每个点在 Prufer 序列中一定恰好出现了 $d_i - 1$ 次，所以度数确定时 Prufer 序列的数字组成也确定了，然后就是多重集组合数了。

所以答案为：

$$ \frac{(n -2)!}{\prod_{i = 1} ^ {n}(d_i - 1)!} $$

连接连通块方案数

有一个有标号图，其中有 $k$ 个连通块，各连通块节点个数为 $s_1, \cdots, s_k$，求连 $k - 1$ 条边，使其成为一个连通块的方案数。

把每个连通块看成一个点，则最后的形态是一棵树。设 $d_i(T)$ 是在树 $T$ 上的度数，那么方案数是 $\sum_T\prod s_i ^ {d_i(T)}$。$d_i -1$ 等于其在 Prufer 序列中的出现次数，于是拆一下：

$$ \sum_T \prod s_i ^ {d_i(T)} = (\prod s_i) (\sum_T \prod s_i ^ {d_i(T)- 1}) $$

设与 $T$ 对应的 Prufer 序列是 $a_1, \cdots, a_{k - 2}$，则右边那个等于

$$ \sum_{所有序列 a} \prod_{t = 1} ^ {k - 2} s_{a_t} = (s_1 + \cdots + s_k) ^ {k - 2} $$

（这一步说明：因为所有 $a$ 是所有 $a_i \in [1, k]$ 的序列个数，然后就相当于从 $s_1 \sim s_k$ 里选 $k - 2$ 个数乘起来。）

代入到上面的式子里，答案就是：

$$ (\sum_{i = 1} ^ k s_i) ^ {k - 2} \times \prod_{i = 1} ^ k s_i $$

BZOJ4766 / 完全二分图生成树个数

题意：求左部有 $n$ 个点，右部有 $m$ 个点的带标号完全二分图的生成树个数。

设左部的点集是 $A$，右部是 $B$。首先最后剩下两个点之间有边，所以一定属于不同集合。考虑 Prufer 序列，$A$ 集合有 $n - 1$ 个点被删除，$B$ 集合的数总共要被加入 $n - 1$ 次，所以这部分方案数是 $m^{n - 1}$；同理，$B$ 集合有 $m - 1$ 个点被删除，$A$ 集合的数要被加入 $m - 1$ 次，所以这部分方案数是 $n ^ {m - 1}$。

所以答案是 $n ^ {m - 1} m ^ {n - 1}$。

Bonus Track：完全三部图的生成树个数：$n(a + b)^{c -1}(a + c) ^ {b - 1} (b + c) ^ {a - 1}$。

如此可以导出完全 $K$ 部图的生成树个数：

$$ n^{K - 2} \prod_{i = 1} ^ {K} (n - n_i) ^ {n_i - 1} $$

证明暂时不会，咕咕咕。

---

• 分类： OI
• 标签： 无标签