符号化方法

符号化方法（symbolic method）是将组合对象快速转换成生成函数的一种方法，我们将考虑对于集合上定义的特定运算，然后导出其对应的生成函数的运算。

我们称一个组合类（或简称为类）为 ，其中 为组合对象的集合，函数 将每一个组合对象映射为一个非负整数，一般称为大小函数。需要注意的是这个非负整数不能是无限大的。例如对于字符集为 的字符串，可以将字符串的长度设置为其大小函数；对于树或图可将节点的数量设置为其大小函数，注意这并非绝对，也可能将某些特定节点的大小函数设置为 等。

本文是基于 Analytic Combinatorics 一书第一章的简化。

无标号体系

在无标号体系中将使用普通生成函数（OGF）。对于集合 其对应 OGF 记为

我们约定使用同一组的字母表示同一个类对应的生成函数等，例如用 表示 即 中 的系数，用 表示 中大小函数为 的对象的集合（所以 其中 为基数（cardinality））。

本文将不讨论可容许性（admissibility），读者可参考文献中的内容。

下面将引入两种特殊的组合类和组合对象：

• 记 为中性对象（neutral object）和 为中性类（neutral class），中性对象的大小为 ，中性类的 OGF 为 。
• 记 或 为原子对象（atom object）和 或 或简写为 为原子类（atom class），原子对象的大小为 ，原子类的 OGF 为 。

对于两个组合类 和 在组合意义上同构记为 或 ，但仅当该同构不平凡时才使用后者的记号。

我们有

其中 为二元运算，表示集合的笛卡尔积。

集合的（不相交）并构造

对于类 和 的并记为

如此定义可以不违背集合论中集合不相交的要求，我们可以想象成将 中的对象染色成红色，将 中的对象染色成蓝色。

对应 OGF 为

考虑

对应形式幂级数的加法。

集合的笛卡尔积构造

对于类 和 的笛卡尔积记为

对应 OGF 为

我们定义 的大小为其组成部分的大小之和，那么显然也有

所以

对应形式幂级数的乘法。

集合的 Sequence 构造

Sequence 构造生成了所有可能的组合。

我们定义

且要求 ，也就是 中没有大小为 的对象。

对应 OGF 为

其中 为 Pólya 准逆（quasi-inversion）。

集合的 Multiset 构造

Multiset 构造生成了所有可能的组合，但不区分组成部分的元素之间的顺序。

我们定义其递推式为

即

且要求 。或者也可以给出等价的

其中 为等价关系，我们说 当且仅当存在任一置换 对于所有 满足 。

对应 OGF 为

注意到

且 所以

其中 为 Pólya 指数，也被称为 Euler 变换。

集合的 Powerset 构造

Powerset 构造生成了所有子集。

我们定义其递推式为

即

且要求 。

对应 OGF 为

其中 为 Pólya 指数·改。

容易发现 。

集合的 Cycle 构造

Cycle 构造生成了所有可能的组合，但不区分仅轮换不同的组合。

我们定义为

其中 为等价关系，我们说 当且仅当存在任一循环移位 对于所有 都满足 。

对应 OGF 为

其中 为 Euler 函数， 为 Pólya 对数。

由于证明较复杂，读者可参考 Flajolet 的论文 The Cycle Construction 或 Analytic Combinatorics 的附录。

有限制的构造

对于上述所有构造，我们都没有限制其「组成部分」的个数，若在 的下标给一个作用于整数的谓词用于约束其组成部分，如

其中 也常简写为 ， 表示在区间 上。

令 为任意上述 之一，以及

即我们需要对于 有

设 函数作用于组合对象上为其组成部分的个数，也就是要令 ，不妨增加一元来「跟踪」组成部分的个数。

令

那么

然后我们只要提取出 的系数即可获得对应表达式，例如 可直接导出

显然也有

而对于 和 已经有

和

对于 同理。

我们发现 中 是关于 的一个表达式。

需要注意的是对于有限制的构造 并没有要求 。

上面的计算方法虽然有效但比较麻烦，读者可阅读 WolframMathWorld 网站的 Pólya Enumeration Theorem 和 Cycle Index 等相关资料，后者 Cycle Index 在 OEIS 的生成函数表达式中也经常出现。

参考文献

• Philippe Flajolet and Robert Sedgewick.Analytic Combinatorics.