如何求完全图生成树个数？
喵仔牛奶
·
·
算法·理论
羡慕你们会 Cayley 公式的。羡慕你们会 Prüfer 序列的。这两个本萌新都不会，怎么办？
不过萌新刚刚看了 详细揭秘：低秩矩阵分解与矩阵树定理极简证明，于是想用这个来求一下 K_n 的生成树个数。
完全图生成树计数
度数矩阵 D_{i,j}=[i=j](n-1)，邻接矩阵 A_{i,j}=-[i\neq j]。去掉第一行。
枚举 S\subseteq\{1,2,\cdots,n-1\}，S 中的行取 A，剩下的行取 D。容斥系数的指数等于每个环环长减一的和。
那么对于 i\notin S，显然有 p_i=i，这部分贡献是 (n-1)^{n-1-\lvert S\rvert}。
剩下部分的话，连边 i\to p_i 形成若干环，要求不能有大小为 1 的环。如果连出了 k 个环，那么对容斥系数贡献是 (-1)^{\lvert S\rvert-k}，然后 A_{i,j} 的积是 (-1)^{\lvert S\rvert}，因此贡献就是 (-1)^k。
那么这个怎么求呢？长度为 n 的环的权值是 -[n\ge 2]，上生成函数，环带权值的生成函数：
C(x)=-\sum_{n\ge 2}\frac{x^n}{n}=x+\ln(1-x)
因此我们的答案就是 [x^{\lvert S\rvert}](\exp C)=[x^{\lvert S\rvert}](e^x-xe^{x})=1-\lvert S\rvert。
那么我们就得到了 K_n 的生成树个数等于：
\begin{aligned}
&\sum_{i=0}^{n-1}\binom{n-1}{i}(n-1)^{n-1-i}(1-i)\\
=&\left(\sum_{i=0}^{n-1}\binom{n-1}{i}(n-1)^{i}i\right)+(2-n)\left(\sum_{i=0}^{n-1}\binom{n-1}{i}(n-1)^{i}\right)\\
=&(n-1)^2\left(\sum_{i=1}^{n-1}\binom{n-2}{i-1}(n-1)^{i-1}\right)+(2-n)n^{n-1}\\
=&(n-1)^2n^{n-2}+(2-n)n^{n-1}\\
=&n^{n-2}\\
\end{aligned}
什么你说直接把所有行加到第一行然后把剩下行消掉就可以推出来了，根本不用这么麻烦？那我说，你说得对。
完全多部图生成树计数
完全多部图就是，给一个序列 \{a_n\}，然后有 n 部分，第 i 个部分 a_i 个点，然后不同部分的点直接连边。记 N=\sum a_i，a'_i=a_i-[i=1]。在 a_1 里面去掉一行。
显然同一部分不能选两行，枚举选了行的部分组成的集合 S，答案为：
\begin{aligned}
&\sum_{S\subseteq\{1,2,\cdots,n\}}\left(\prod_{i\in S}a'_i(N-a_i)^{a'_i-1}\right)\left(\prod_{i\notin S}(N-a_i)^{a'_i}\right)(1-\lvert S\rvert)\\
&=\left(\prod_{i=1}^n(N-a_i)^{a'_i}\right)\sum_{S\subseteq\{1,2,\cdots,n\}}(1-\lvert S\rvert)\prod_{i\in S}\frac{a'_i}{N-a_i}
\end{aligned}
考虑求后面那个和式。令 b_i=\frac{a'_i}{N-a_i}，F(x)=\prod(1+b_ix)，那么答案就是 F(1)-F'(1)。
显然 F(1)=\prod(1+b_i)，F'(1)=F(1)\sum\frac{b_i}{1+b_i}=F(1)\sum\frac{a'_i}{N-a_i+a'_i}=F(1)(1-\frac{a_1}{N}+\frac{a_1-1}{N-1})。
那么：
\begin{aligned}
F(1)-F'(1)=&\big(1-\frac{F'(1)}{F(1)}\big)\cdot F(1)\\
=&\frac{N-a_1}{N(N-1)}\cdot(n-1)N^{n-1}\prod_{i=1}^{n}\frac{1}{N-a_i}\\
=&(N-a_1)N^{n-2}\prod_{i=1}^{n}\frac{1}{N-a_i}\\
\end{aligned}
因此答案即为：
\begin{aligned}
N^{n-2}\prod_{i=1}^n(N-a_i)^{a_i-1}
\end{aligned}
伟大的 @cjZYZtcl 给出了后面部分的另一种推导。