组合类的集合构造 | Codeboy's Blog

形式陈述

在组合计数的符号方法中，对没有大小零对象的组合类 $\mathcal B$ ，标号集合构造 $\operatorname{SET}(\mathcal B)$ 把总标签集划分成若干非空块，在每块上放一个 $\mathcal B$ -结构，并忽略组件次序。若 $B(z)$ 是 EGF，则

\operatorname{SET}_k(\mathcal B)\longleftrightarrow \frac{B(z)^k}{k!}, \qquad \operatorname{SET}(\mathcal B)\longleftrightarrow \exp(B(z)).

这是组合物种代入 $E\circ B$ 的标号形式。

无标号组件允许同一种结构类型重复时，正确构造通常记为 $\operatorname{MSET}(\mathcal B)$ 。若 $b_n$ 是大小为 $n$ 的组件类型数，OGF 为

\prod_{n\ge1}(1-z^n)^{-b_n} =\exp\left(\sum_{k\ge1}\frac{B(z^k)}k\right).

若每种无标号类型至多出现一次，则是 $\operatorname{PSET}$ ，其 OGF 为

\prod_{n\ge1}(1+z^n)^{b_n} =\exp\left(\sum_{k\ge1}\frac{(-1)^{k-1}}kB(z^k)\right).

这些 $z^k$ 修正来自Pólya 枚举，不能删去。

直觉

集合构造的组件没有第一、第二之分。标号情形中，标签把组件实例区分开来，除以 $k!$ 恰好消去组件排列；把所有 $k$ 相加便得到指数。无标号情形中，同型组件之间存在真实对称，必须逐种类型记录重数，因而出现 Euler 乘积或循环指标。

“SET 对应指数”只对标号 EGF 无条件呈现为 $\exp(B)$ 。若把同一句口号搬到无标号 OGF，就会把对称轨道当成彼此独立的标号组件，通常得到错误系数。

例子与边界

令 $\mathcal B$ 对每个正整数 $m$ 恰有一个大小为 $m$ 的无标号对象，故

B(z)=z+z^2+\cdots=\frac z{1-z}.

其多重集合选择就是整数分拆：选择大小 $m$ 的对象 $r$ 次，表示部分 $m$ 出现 $r$ 次。因此

\operatorname{MSET}(\mathcal B) \longleftrightarrow \prod_{m\ge1}\frac1{1-z^m}.

例如 $z^4$ 的五种贡献对应 $4,3+1,2+2,2+1+1,1+1+1+1$ 。若误用 $\exp(z/(1-z))$ ，其系数带有 $1/k!$ 权重，既不再是整数分拆数，也没有正确处理相同部分的重数。

标号集合的典型例子是集合划分：

\operatorname{SET}\bigl(\operatorname{SET}_{\ge1}(\mathcal Z)\bigr) \longleftrightarrow \exp(e^z-1).

内层非空集合是一块，外层集合忽略块次序。按 EGF 约定把 $z^n$ 的系数乘回 $n!$ ，得到计数 $1,1,2,5,\ldots$ ，其中 $5$ 正是三标签集合的五个划分。

若 $\mathcal B$ 含空结构，物种代入的“非空块”解释失效，形式公式的常数项会出现 $e^{B(0)}$ 而不再对应有限集合计数。若组件间还存在邻接或相容限制，也不能用自由 SET，必须把限制写进新结构或使用图、超图等更细规格。

推论与应用

SET 是“整体由无序连通组件组成”的通用语法。标号图是连通标号图的集合，排列是标号循环的集合，映射图也按连通函数图分解。由此产生组合指数公式 $A(z)=\exp(C(z))$ 。

加入变量 $u$ 标记组件数可得 $\exp(uB(z))$ ；对 $u$ 求导或取 $[u^k]$ 可研究组件数量。无标号版本则变成

\exp\left(\sum_{j\ge1}\frac{u^jB(z^j)}j\right),

其中 $u^j$ 记录循环指标中的重复轨道，不能简单写成 $\exp(uB(z))$ 。

参考资料

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Chapters I–II, multiset and labelled set constructions。
François Bergeron, Gilbert Labelle, and Pierre Leroux, Combinatorial Species and Tree-like Structures, Cambridge University Press, 1998, Chapters 1–2。
George Pólya and Robert C. Read, Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer, 1987, Chapters 1–2。