组合类 | Codeboy's Blog

形式陈述

组合类是带有大小映射的对象集合

|\cdot|:\mathcal A\longrightarrow\mathbb N,

并要求每个大小层

\mathcal A_n=\{\alpha\in\mathcal A:|\alpha|=n\}

都是有限集。记 $a_n=|\mathcal A_n|$ ，则其普通生成函数为

A(z)=\sum_{\alpha\in\mathcal A}z^{|\alpha|} =\sum_{n\ge0}a_nz^n.

这里首先按形式幂级数理解；“每层有限”保证每个系数确实是有限整数。对象的大小通常是原子数、顶点数或总权重，但必须在定义类时固定。若给对象附加权重 $w(\alpha)$ ，还可写成 $A(z)=\sum_\alpha w(\alpha)z^{|\alpha|}$ ，前提是每个次数的总和有定义。

两个基础类常记为 $\mathbf 1$ 与 $\mathcal Z$ ： $\mathbf 1$ 只有一个大小为零的空对象，生成函数为 $1$ ； $\mathcal Z$ 只有一个大小为一的原子，生成函数为 $z$ 。复杂组合类由它们经不交并、笛卡尔积、序列、集合或循环等构造生成。

直觉

组合类把“要数什么”与“怎样计算”分开。对象可以是树、词、分拆或图；大小映射把不同形状放进同一层，生成函数只记录每层有多少对象。它像一份按尺寸整理的目录：系数告诉我们库存量，却不会抹去对象本身的分解结构。正是那份结构，随后允许把类的构造翻译成生成函数运算。

通常所谓无标号类，是把对象看成结构类型而不保留原子的个人身份。例如长度为 $n$ 的二进制词仍有 $2^n$ 个，因为位置次序属于结构；“无标号”不等于“所有原子都可以任意交换”。是否同一对象取决于事先规定的同构概念，而不是看到相同大小就合并。

例子与边界

令 $\mathcal W$ 为有限二进制词，大小取词长。第 $n$ 层含 $2^n$ 个词，所以

W(z)=\sum_{n\ge0}2^nz^n=\frac1{1-2z}.

这一等式在形式意义下由 $(1-2z)W(z)=1$ 验证。长度三的八个对象确实可逐个列出，从“000”到“111”；系数 $8$ 来自两种字母在三个有序位置上的独立选择，而不是把数字机械代入公式。

整数分拆也构成组合类，大小是各部分之和，第 $n$ 层有 $p(n)$ 个对象。它的生成函数是无限乘积而非有理函数，说明“组合类”只提供可计数分层，不承诺闭式、递推或容易计算。

若某一层含无限多个对象，例如给每个大小一对象再附上任意实数颜色，则普通整数系数生成函数失去意义。另一个边界是大小零对象：单独存在有限多个没有问题，但对它们作任意长序列会在大小零层制造无限多个结果。因此类本身局部有限，并不保证每一种复合构造仍局部有限。

相同生成函数也不意味着组合类同构。二进制词与某些着色路径都可有系数 $2^n$ ，但它们的自然分解、参数和对称性不同；生成函数是计数投影，不是对象的完整身份证。

推论与应用

组合类是不交并与乘法原理的统一载体。若 $\mathcal A=\mathcal B\uplus\mathcal C$ 是真正不交的分解，则 $A=B+C$ ；若每个对象唯一分解为一对大小相加的对象，则 $A=BC$ 。唯一性和局部有限性是等式的见证，不能只因右侧形式好看便反推结构分解。

组合计数的符号方法把这些结构等式系统化，并为 SEQ、SET、CYC 等构造给出生成函数字典。带标号对象需要使用标号组合类及阶乘归一化；若还要把“在任意有限标签集上搬运结构”形式化，则进入组合物种。得到形式生成函数之后，再增加收敛和复解析条件，才能用奇点或鞍点估计系数。

参考资料

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Chapter I, combinatorial classes and ordinary generating functions。
Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011, Chapter 1, generating functions and combinatorial interpretations。
Herbert S. Wilf, generatingfunctionology, 3rd ed., A K Peters, 2006, Chapters 1–2。