一些有关树的结论【随机树树高】【完全图生成树个数】【连接连通块方案数】【Prüfer 序列】【Prufer 序列】
zhiyin123
·
·
算法·理论
随机树树高
问题描述：对于一棵以 1 为根，n 个节点的树（索引从 1 到 n），随机生成方式如下，问其期望树高。
- 对于节点 i（i>1），f 为 [1,i) 中均匀随机生成的整数，令 f 为 i 的父节点。
结论：树高为 O(\log n)。
预备知识：
\int \log(x)\mathrm{d}x= x(\log(x)-1)+C
其中 C 为常数。
解说：不妨设期望树高为 a_n（n\geq 1），则由平凡情况（n=1）和期望的线性性得
\begin{gathered}
a_1=1\\
a_{n+1}=1+\frac{1}{n}\sum_{i=1}^na_i
\end{gathered}
现在，我们证明，存在常数 C，使得 a_n\leq C\ln(n)。
使用归纳法，显然，当 n\leq 1 时满足。
假设，当 n\leq k 时满足，那么，k+1 的情况有
\begin{gathered}
a_{k+1}=1+\frac{1}{k}\sum_{i=1}^ka_i\\
\leq 1+\frac{C}{k}(\ln(1)+\ln(2)+\cdots+\ln(k))\\
\leq 1+\frac{C}{k}\int_1^{k+1}\ln(t)\mathrm{d}t\\
=1+\frac{C}{k}((k+1)\ln(k+1)-k)\\
=C\ln(k+1)+\frac{C\ln(k+1)}{k}+1-C
\end{gathered}
显然，C 存在合理取值，使得 \displaystyle \frac{C\ln(k+1)}{k}+1-C\leq 0 在 k 取遍 \mathbb N^+ 时成立，故
a_{k+1}\leq C\ln(k+1)
证毕。
2025.01.30 更新。
更好的证明：（思路来自 DeepSeek R1）
上面的证明纯🤡。
首先，还是沿用上面的式子
\begin{gathered}
a_1=1\\
a_{n+1}=1+\frac{1}{n}\sum_{i=1}^na_i
\end{gathered}
直接硬算 a 的差分，有
\begin{gathered}
a_{n + 2} - a_{n + 1} = \left(1 + \frac{1}{n + 1}\sum_{i = 1} ^ {n + 1} a_i\right) - \left(1 + \frac{1}{n}\sum_{i = 1} ^ n a_i\right)\\
=\frac{1}{n + 1}a_{n + 1} + \left(\frac{1}{n + 1} - \frac{1}{n}\right)\sum_{i = 1} ^ n a_i\\
=\frac{1}{n + 1}a_{n + 1} - \frac{1}{n(n + 1)}\sum_{i = 1} ^ n a_i\\
=\frac{1}{n + 1}\left(1 + \frac{1}{n}\sum_{i = 1} ^ n a_i\right) - \frac{1}{n(n + 1)}\sum_{i = 1} ^ n a_i\\
=\frac{1}{n + 1}
\end{gathered}
于是，有
a_{n + 2} = a_2 + \sum_{i = 1} ^ {n + 1}\frac{1}{i}
设调和级数的第 i 项为 H_i，特别的，H_0 = 0，则
\boxed{a_n = 1 + H_{n - 1}}
这就直接说明了 a_n 是 O(\log n) 的。
完全图生成树个数
\boxed{n^{n-2}}
（其中 n 为节点个数）
连接连通块方案数
有一个有标号图，其中有 k 个连通块，各连通块节点个数为 s_1,s_2,\dots,s_k，连 k-1 条边，使其成为一个连通块的方案数为
\boxed{\left(\sum s_i\right)^{k-2}\prod s_i}
可以考虑 Prüfer 序列建树的过程。