组合指数公式 | Codeboy's Blog

形式陈述

设 $\mathcal C$ 是没有空对象的标号组件类，每个 $\mathcal A$ -对象都能唯一分解成一组标签互不相交、并集为总标签集的 $\mathcal C$ -组件。组合上写作

\mathcal A=\operatorname{SET}(\mathcal C).

若

C(z)=\sum_{n\ge1}c_n\frac{z^n}{n!}, \qquad A(z)=\sum_{n\ge0}a_n\frac{z^n}{n!},

A(z)=\exp(C(z)), \qquad C(z)=\log A(z),

并有 $a_0=1$ 。系数形式为

a_n=\sum_{\pi\in\Pi([n])} \prod_{B\in\pi}c_{|B|},

其中 $\Pi([n])$ 是标签集的全部集合划分。等价地，

\frac{a_n}{n!} =\sum_{\substack{m_1,m_2,\ldots\ge0\\ \sum j m_j=n}} \prod_{j\ge1}\frac1{m_j!} \left(\frac{c_j}{j!}\right)^{m_j}.

整数 $m_j$ 记录大小 $j$ 的组件数， $m_j!$ 消去同大小组件的排列。

直觉

指数公式把“连通”与“任意”之间的关系说到系数级别。先把标签集分块，每块承载一个连通组件；块没有先后次序，因此总体是组件的 SET。指数级数中的 $1/k!$ 正好消去 $k$ 个组件的排列，而 EGF 的 $1/n!$ 负责标签分配。

取对数则做相反工作：它从允许任意多个组件的总体类中抽出单个连通块。这里的“连通”可以是图论连通，也可以泛指规格所指定的不可再分组件；只要分解唯一且权重按组件相乘，公式都成立。

例子与边界

令 $g_n=2^{\binom n2}$ 为 $[n]$ 上简单图总数， $c_n$ 为连通简单图数。每张图按连通分量唯一分解，所以

G(z)=\sum_{n\ge0}2^{\binom n2}\frac{z^n}{n!} =\exp\left(\sum_{n\ge1}c_n\frac{z^n}{n!}\right).

对 $n=3$ ，共有 $g_3=8$ 张图。非连通情形要么三个孤立点，贡献 $1$ ；要么一条边加一个孤立点，选择孤立点有 $3$ 种。因此

8=c_3+3c_2c_1+c_1^3=c_3+3+1,

得到 $c_3=4$ 。这个小规模核算展示了集合划分公式中的每一项来自哪种组件型，而非仅把 $G$ 取对数。

无标号对象不能照搬 $A(z)=e^{C(z)}$ 。若总体是无标号组件的多重集合，正确 OGF 是

A(z)=\exp\left(\sum_{k\ge1}\frac{C(z^k)}k\right).

另外，若分解不唯一、组件允许共享标签、权重不按组件相乘，或存在可任意重复的空组件，指数公式的组合证明都会断裂。

推论与应用

指数公式统一了大量经典恒等式：集合划分满足 $\exp(e^z-1)$ ；排列由循环的集合构成，得到 $\exp(\log(1/(1-z)))$ ；标号图的对数生成连通图。若用变量 $u$ 标记组件数，则

A(z,u)=\exp(uC(z)),

其 $[u^k]$ 项恰对应含 $k$ 个组件的对象。由此可推导组件数的阶乘矩、概率生成函数及极限分布。

在带权情形，只要对象权重等于组件权重乘积，同一公式仍在相应系数环中成立。它既是物种代入 $E\circ C$ 的投影，也是簇展开、随机结构与统计物理中“自由组件气体”公式的组合原型。

参考资料

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Chapter II, labelled set construction and the exponential formula。
François Bergeron, Gilbert Labelle, and Pierre Leroux, Combinatorial Species and Tree-like Structures, Cambridge University Press, 1998, Chapters 1–2。
Richard P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999, §5.1, the exponential formula。