符号化方法
符号化方法(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 Theorem 和 Cycle Index 等相关资料,后者 Cycle Index 在 OEIS 的生成函数表达式中也经常出现。
例题 LOJ 6538. 烷基计数 加强版 加强版
题意:求出 个节点的有根且根节点度数不超过 ,其余节点度数不超过 的无序树的个数对 取模的值。约定 。
解:设组合类为 那么
或令组合类 那么
可得到相同的结果。
参考文献
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用