符号化方法

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

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

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

无标号体系

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

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

本文将不讨论可容许性(admissibility),读者可参考文献中的内容。

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

  • 为中性对象(neutral object)和 为中性类(neutral class),中性对象的大小为 ,中性类的 OGF 为
  • 为原子对象(atom object)和 或简写为 为原子类(atom class),原子对象的大小为 ,原子类的 OGF 为

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

我们有

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

集合的(不相交)并构造

对于类 的并记为

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

对应 OGF 为

考虑

对应形式幂级数的加法。

集合的笛卡尔积构造

对于类 的笛卡尔积记为

对应 OGF 为

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

所以

对应形式幂级数的乘法。

集合的 Sequence 构造

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

可以看到 这样组成部分的顺序不同的元素被生成了,可以认为 Sequence 构造生成了有序的组合。

我们定义

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

对应 OGF 为

其中 为 Pólya 准逆(quasi-inversion)。

例:有序有根树(ordered rooted tree)

我们可以使用 Sequence 构造来定义有序有根树,即孩子之间的顺序有意义的有根树,设该组合类为 那么一棵树为一个根节点和树的 Sequence,即

对应 OGF 为

前几项系数为 0 1 1 2 5 14 42 132 429 1430 4862 16796,忽略常数项即 OEIS A000108

集合的 Multiset 构造

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

注意到 中出现,但在 没有出现,可以认为 Multiset 生成了无序的组合。

我们定义其递推式为

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

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

对应 OGF 为

注意到

所以

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

例题 LOJ 6268. 分拆数

题意:令 表示将 进行分拆的方案数,求 取模的值。

:设全体正整数类为 ,那么 (下标 为有限制的构造,见后文)。所求即

对应 OGF 前几项系数为 1 2 3 5 7 11 15 22 30 42(忽略常数项)即 OEIS A000041

例题 洛谷 P4389 付公主的背包

题意:给出 种体积分别为 的商品和正整数 ,求体积为 的背包装满的方案数(商品数量不限,有同体积的不同种商品)对 取模的值。约定

:设商品的组合类为 ,所求即 对应 OGF 的系数。

例题 洛谷 P5900 无标号无根树计数

题意:求出 个节点的无标号无根树的个数对 取模的值。约定

:设无标号有根树的组合类为 ,那么

根据 Richard Otter 的论文 The Number of Trees 中的描述,对应无根树的 OGF 为

前几项系数为 1 1 1 2 3 6 11 23 47 106(忽略常数项)即 OEIS A000055

集合的 Powerset 构造

Powerset 构造生成了所有子集。

我们定义其递推式为

且要求

对应 OGF 为

其中 为 Pólya 指数·改。

容易发现

集合的 Cycle 构造

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

我们定义为

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

为了简便我们令 均为大小为 的字符,这里仅列举大小为 的字符串:

其中 只保留其一,同样的 只保留其一。

其中

对应 OGF 为

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

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

有限制的构造

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

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

为任意上述 之一,以及

即我们需要对于

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

那么

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

显然也有

而对于 已经有

对于 同理。

使用上式计算 对应 OGF

尝试计算

尝试计算

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

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

常用有限制的构造

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

例题 LOJ 6538. 烷基计数 加强版 加强版

题意:求出 个节点的有根且根节点度数不超过 ,其余节点度数不超过 的无序树的个数对 取模的值。约定

:设组合类为 那么

或令组合类 那么

可得到相同的结果。

参考文献