Cayley 定理
一棵有标号生成树唯一对应着一个 prufer 序列。
任意一个长度为 \(n-2\)、值域为 \([1,n]\) 的序列也唯一对应着一棵大小为 \(n\) 的有标号生成树。
若一个点 \(u\) 在 prufer 序列中出现 \(d\) 次，那么它在树上的度数为 \(d+1\)。
扩展 Cayley 定理
考虑若干个大小分别为 \(s_1,s_2,\cdots,s_k\) 的连通块（它们都是树），且满足 \(\sum s_i=n\)，我们需要连 \(k-1\) 条边让这若干个连通块构成一棵树，求能得到多少有标号无根树。
假瑞说按生成函数推很顺手：考虑将每个连通块当成一个大点，那么我们肯定是连 \(k-1\) 条边让这 \(k\) 个大点构成一棵树，这 \(k\) 个大点构成的树会对应一个长度为 \(k-2\)、值域为 \([1,k]\) 的 prufer 序列，我们考虑枚举这 \(k\) 个大点的度数，即在 prufer 序列中出现的次数：
\[ans=\sum_{d_1+\cdots+d_k=k-2}\dfrac{(k-2)!}{d_1!\cdots d_{k}!}\prod_{i=1}^ks_i^{d_i+1} \]设 \(F_i(x)=\sum\limits_{d\geq 0}\dfrac{s_i^{d+1}}{d!}x^d=s_i\sum\limits_{d\geq 0}\dfrac{s_i^d}{d!}x^d=s_ie^{s_ix}\)，那么：
\[\begin{aligned} ans&=(k-2)!\sum_{d_1+\cdots+d_k=k-2}\prod_{i=1}^k[x^{d_i}]F_i(x)\\ &=(k-2)![x^{k-2}]\prod_{i=1}^kF_i(x)\\ &=(k-2)![x^{k-2}]\prod_{i=1}^ks_ie^{s_ix}\\ &=(k-2)!\prod_{i=1}^{k}s_i[x^{k-2}]e^{(\sum s_i)x}\\ &=(k-2)!\prod_{i=1}^k s_i[x^{k-2}]e^{nx}\\ &=n^{k-2}\prod_{i=1}^ks_i \end{aligned} \]听说这种生成函数推导方法很普遍适用。
\(k\) 部完全图的生成树计数问题
对于 \(N\) 个点的 \(k\) 部图 \(G\)，设其第 \(i\) 部有 \(n_i\) 个点，任意不同部的两点之间都有一条边相连。那么图 \(G\) 的生成树个数为：
\[N^{k-2}\prod_{i=1}^k(N-n_i)^{n_i-1} \]证明：矩阵树定理的证明和 prufer 序列的证明均给出了。
矩阵树定理
即求下面这个矩阵的行列式：（注意由于抽掉了一行一列，矩阵行列数为 \(N-1\)）
我们将它拆成 \(A+B\)，其中 \(B\) 是全 \(-1\) 矩阵，那么：
\[\begin{aligned}\det(A+B)&=\sum_{p}(-1)^{\operatorname{sgn}(p)}\prod_{i}(A_{i,p_i}+B_{i,p_i})\\&=\sum_{p}(-1)^{\operatorname{sgn}(p)}\sum_{S\subset \{1,\cdots,N-1\}}\prod_{i\in S}A_{i,p_i}\prod_{i\not\in S}B_{i,p_i}\\&=\sum_{S\subset\{1,\cdots,n\}}\sum_{p}(-1)^{\operatorname{sgn}(p)}\prod_{i\in S}A_{i,p_i}\prod_{i\not\in S}B_{i,p_i}\end{aligned} \]考虑 \(\sum_{p}(-1)^{\operatorname{sgn}(p)}\prod_{i\in S}A_{i,p_i}\prod_{i\not\in S}B_{i,p_i}\) 的含义，实际上就是把 \(A\) 中属于 \(s\) 的那些行、以及 \(B\) 中不属于 \(s\) 的那些行抽出来拼成一个新的矩阵，然后求这个新矩阵的行列式。
那么若从 \(B\) 中至少抽出了两行，那么新矩阵中就会有两行全为 \(-1\)，此时该矩阵行列式一定为 \(0\)。
即我们只需考虑 \(|S|\geq N-2\)，即至多从 \(B\) 中抽出一行的情况。
先考虑 \(|S|=N-2\) 的情况，我们即求如下左矩阵的行列式：
我们先关注左上角的 \((n_1-1)\times(n_1-1)\) 的子矩阵：显然可以对前 \(n_1-1\) 行操作将该子矩阵消成对角矩阵，再通过消出来的这 \(n_1-1\) 行把那行 \(-1\) 的前 \(n_1-1\) 列全消了，然后再将前 \(n_1-1\) 行复原回原来的样子。类比地，我们能将整个矩阵通过如上方式转化成右边的矩阵。
此时整个矩阵的行列式等于对角线上各个子矩阵的行列式之积，而对角线上各个子矩阵的行列式是好求的。
枚举 \(-1\) 所在的行即可得到 \(|S|=N-2\) 的结果，然后再加上 \(|S|=N-1\)，经过化简即可得到结论。
prufer 序列
仍然是考虑构造双射。如果用普通的 prufer 序列，树 \(\to\) prufer 不会有问题，但问题是不一定每一种 prufer 序列都能映射到树。
会出现的问题是：当我们取出全局编号最小的叶子，要和当前 prufer 序列的第一位连边时，会发现二者可能在同一部。
为了避免该问题，我们采用如下的映射方法：（设所有点构成的集合为 \(V\)，第 \(i\) 部点构成的集合为 \(V_i\)）
-
树 \(\to\) prufer：初始先建立 \(k+1\) 个空序列 \(A_1,\cdots,A_k,B\)。然后重复如下过程直到图中仅剩两点为止：
每次选择全局编号最小的叶子，记为 \(u\)，设 \(u\) 在第 \(i\) 部。记 \(u\) 父亲为 \(f\)。
-
若 \(u\) 不为当前第 \(i\) 部内最后一个点，则将 \(f\) 插入到 \(A_i\) 末尾。
-
否则，将 \(f\) 插入到 \(B\) 末尾。
将 \(u\) 从图中删去。
-
-
prufer \(\to\) 树：只需证明对于任意满足 \(A_i\) 长度为 \(n_i-1\)、\(B\) 长度为 \(k-2\)、\(A_i\) 中元素属于 \(V\setminus V_i\)、\(B\) 中元素属于 \(V\) 的 prufer 序列，都能映射回一棵合法的树即可。
初始先建立一个集合 \(S=\{1,\cdots,n\}\)。重复如下过程直到 \(A_1,\cdots,A_k,B\) 均为空为止：
找到 \(S\) 中未在 \(A_1,\cdots,A_k,B\) 中出现的编号最小的点，记为 \(u\)，设 \(u\) 在第 \(i\) 部。
-
若 \(A_i\) 非空，则将 \(u\) 和 \(A_i\) 的第一个元素连边，并将 \(A_i\) 的第一个元素从 \(A_i\) 中删去。
-
否则，将 \(u\) 和 \(B\) 的第一个元素连边，并将 \(B\) 的第一个元素从 \(B\) 中删去。
由于 \(A_i\) 为空，则证明存在 \(n_i-1\) 个不同的第 \(i\) 部节点，它们之前都未在 \(A_1,\cdots,A_k,B\) 中出现，那么取出的 \(B\) 的第一个元素，它肯定不是第 \(i\) 部的点，所以不会出问题。
-
至此，我们构造了一个树和 prufer 序列之间的双射。同时也容易看出，此时每个点在 prufer 序列中出现的次数同样是它的度数减 \(1\)。
钦定每点度数的 \(k\) 部完全图的生成树计数问题
open problem (in my blog)
至少我推出来只会指数级做法，哪位数数大师来赐教一下/kel
标签：sum,矩阵,cdots,序列,prod,prufer From： https://www.cnblogs.com/ez-lcw/p/16843062.html