n节点的无序标号树有多少种：拉格朗日反演的应用

摘要: 拉格朗日反演的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，本文我们继续来讨论算法分析的问题。

对于图论中的很多算法，其时间复杂度的分析经常需要基于 n 节点的无序标号树共有多少种这个问题。本文我们就来解决这个问题，顺便看一下拉格朗日反演的应用。

在前面的几篇文章中，我们解决了诸如 N 节点二叉树的种类数，快速排序平均比较次数等算法分析中的最基础的问题。在处理这些问题的过程中，我们认识到生成函数往往是解决问题的核心。

通过生成函数解决问题，可以流程化地分为 3 步：

1. 导出生成函数 $T(z)$ 满足的方程。
2. 求解方程得到 $T(z)$。
3. 将 $T(z)$ 展开，取其中 $z^{N}$ 的系数。

在文章 二叉树的计数：直接方法与间接方法 中，我们初步了解了符号方法的应用。引入符号方法后，解决第 1 步就变得比较简单。

第 2 步是求解函数方程或微分方程，这是相对比较完善的数学领域，根据具体的方程，去找相应的内容即可。

对于第 3 步也是有一些非常有力的工具的：拉格朗日反演就是其中一个。本文我们就用拉格朗日反演来解决 n 节点无序标号树个数这个经典问题。

---

问题描述

对于一个 N 节点的图，如果它有 N - 1 条边，并且是连通图，那它就是一棵 N 节点的树。我们的讨论就是在这样的一个结构上展开的。

但是这样的树结构还有很多分类，比如：

• 有根树还是自由树：自由树就是最一般的无环连通图，给定了这个图，指定不同的节点作为根节点如果视为同一棵树，那么称为无根树或自由树；如果指定哪个节点为根需要考虑，那么称为有根树。
• 有序树还是无序树：对于有根树来说，根节点连接了若干子树，修改这些子树连接到根的顺序，所形成的新树如果视为不同的树，则称为有序树；否则子树的顺序不重要，称为无序树，这些子树可以视为另外一些无序树的多重集。
• 标号树还是无标号树：树的节点是否可区分，如果不可区分，称为无标号树；否则节点就有不同标识，称为有标号树。

因此当我们讨论树的问题的时候，首先要明确我们讨论的是什么树。这里我们讨论的是标号有根无序树，也称为 Cayley 树。因为 19 世纪凯莱对该问题做过研究，其结论称为凯莱公式：

凯莱(Cayley)公式

给定 n 个不同的点，组成的无根树的个数为 $n^{n-2}$。

$n^{n-2}$ 给出的是标记无根无序树的计数，由于有根树的计数就是在无根树的计数的基础上，需要从 $n$ 个节点中取一个作为根，有 $n$ 种不同的取法，因此记 $C_{n}$ 为 $n$ 个节点的标记有根无序树，有 $C_{n} = n^{n-1}$，这与上述凯莱公式是一回事。

凯莱公式的证明方法很多，并且有些证法的背后是非常有用的工具，比如矩阵树定理、比如 Prufer 编码，这方面内容可以参考图论相关的书。本文我们看一下基于拉格朗日反演的推导过程。

指数生成函数 $C(z)$ 的函数方程

记 $\mathcal{C}$ 为所有可能的 Cayley 树的集合。其中具有 $N$ 个节点的 Cayley 树的个数记为 $C_{N}$，其指数生成函数为：

$$C(z) = \sum\limits_{N=0}\limits^{\infty}C_{N}\frac{z^{N}}{N!} = \sum\limits_{|c|\in\mathcal{C}}\frac{z^{|c|}}{|c|!}$$

$C(z)$ 所满足的函数方程的推导过程，用到了使用生成函数对组合对象计数的符号方法，其推导过程涉及到一些抽象概念的定义以及相关的定理。

这里我们直接用结果：$C(z) = ze^{C(z)}$。在以后详细介绍符号方法时，我们再回到这里，将上式的推导过程补上。

拉格朗日反演定理

拉格朗日反演定理

如果生成函数 $A(z) = \sum\limits_{n=0}\limits^{\infty}a_{n}z^{n}$ 满足函数方程 $z = f(A(z))$，其中 $f(z)$ 满足 $f(0) = 0$，且 $f’(0) \neq 0$，则：

$$a_{n} = [z^{n}]A(z) = \frac{1}{n}[u^{n-1}](\frac{u}{f(u)})^{n}$$

以及：

$$[z^{n}](A(z))^{m} = \frac{m}{n}[u^{n-m}](\frac{u}{f(u)})^{n}$$

并且：

$$[z^{n}]g(A(z)) = \frac{1}{n}[u^{n-1}]g'(u)(\frac{u}{f(u)})^{n}$$

以上定理的可以追溯到 18 世纪，其证明可以参考组合数学方面的书，例如《分析组合学》。

拉格朗日反演对于幂级数的转换，是非常有力的办法。它最大的特点是在函数的逆函数的系数与函数的幂之间，提供了直接对应关系。对于一些难解的隐函数，可以考虑用拉格朗日反演来提取系数。

---

再看二叉树计数的例子

在文章 二叉树的计数：直接方法与间接方法 中我们讨论过二叉树的计数，我们知道具有 N 个节点的二叉树的函数方程如下：

$$T(z) = 1 + zT^{2}(z)$$

在那篇文章中，我们首先通过二次方程求根公式求解出了 $T(z)$，然后再基于广义二项式定理将结果展开，$T_{n} = [z^{n}]T(z) = \frac{1}{n+1}\binom{2n}{n}$ 给出了具有 N 个节点的二叉树的个数。

而由于原方程可以写为 $zT(z) = z + (zT(z))^{2}$，记 $G(z) = zT(z)$，有 $z = G(z) - G^{2}(z)$，这刚好是拉格朗日反演定理的形式，因此可以取 $f(u) = u - u^{2}$，根据拉格朗日反演，有：

$$[z^{n}]G(z) = \frac{1}{u}[u^{n-1}](\frac{n}{u-u^{2}})^{n} = \frac{1}{n}[u^{n-1}](\frac{1}{1-u})^{n}$$

参考 生成函数的性质速查 中的速查表，可得 $\frac{u^{n-1}}{(1-u)^{n}} = \sum\limits_{k=n-1}\limits^{\infty}\binom{k}{n-1}u^{k}$。因此：

$$[u^{n-1}]\frac{1}{(1-u)^{n}} = [u^{2n-2}]\frac{u^{n-1}}{(1-u)^{n}} = \binom{2n-2}{n-1}$$

因此：

$$[z^{n}]G(z) = \frac{1}{n}\binom{2n-2}{n-1}$$

代回 $T(z)$ 有：

$$[z^{n}]T(z) = [z^{n+1}]G(z) = \frac{1}{n+1}\binom{2n}{n}$$

这与我们之前通过直接解方程然后再进行展开得到的结果一样。不同的是我们通过拉格朗日反演，将 $[z^{n}]T(z)$ 的问题转化为了 $[u^{n-1}]\frac{1}{(1-u)^{n}}$ 的问题，而后者可以通过查表直接得到。

从这个例子可以看出拉格朗日反演的价值，可以将难求展开式系数的函数 $T(z)$ 转化为好求展开式系数的函数，对于本例，该函数是 $\frac{1}{(1-u)^{n}}$。

$C_{n}$ 的解

由于 $C(z) = ze^{C(z)}$，可以写为 $z = C(z)e^{-C(z)}$，这是满足拉格朗日定理的形式，于是可以取 $f(u) = ue^{-u}$，于是立即可以得到：

$$[z^{n}]C(z) = \frac{1}{n}[u^{n-1}]e^{un} = \frac{1}{n}\frac{n^{n-1}}{(n-1)!} = \frac{n^{n-1}}{n!}$$

于是得到凯莱公式：

$$C_{n} = n![z^{n}]C(z) = n^{n-1}$$

这里也看出了拉格朗日反演的作用，将满足方程 $C(z) = ze^{C(z)}$ 的函数 $C(z)$ 的展开式系数的问题，转化为了 $e^{un}$ 的展开式系数的问题，而 $e^{un}$ 的展开式系数是好求的，于是我们甚至没有解方程，就轻易得到了 $C(z)$ 的展开式系数。

总结

本文我们讨论了图论中的算法分析的常见问题：n 节点的无序标号树共有多少个。其结果称为凯莱公式。

本文的推导基于拉格朗日反演，首先介绍了拉格朗日反演定理的描述，然后用该定理重新解决了二叉树计数的问题，可以发现拉格朗日反演在简化生成函数计数问题的价值。

凯莱公式是图论中的经典结论，主流的推导方式有矩阵树定理和 Prufer 编码等，前置的知识都比较冗长。而本文使用拉格朗日反演，非常轻易地就得到了结果。

当然为了突出重点，一些结论本文跳过了推导步骤，比如 n 节点无序标号树的指数生成函数满足的函数方程 $C(z) = ze^{C(z)}$ 是怎么推导出来的；比如拉格朗日反演定理是怎么推导出来的。后续我们再探讨这些问题。

---