组合符号化（下）

发表于 分类于 ， 阅读次数：

本文共约 7100 字。

Key Words：图计数，PGF（概率生成函数），多元生成函数，符号化容斥

图计数选讲

工具已经齐备，现在让我们进军一大类有代表性的经典问题：图计数问题。

无标号图

无标号有序二叉树（卡塔兰数）

记 为无标号有序有根二叉树，有 解得 提取系数得

无标号有序多叉树

无标号有根树

记无标号有根树为 。儿子之间没有顺序之分，一棵树删去根之后是森林（森林是树的无序集合），根据组合意义 可以用牛顿迭代或全在线卷积求解 ，具体方法略。

在此基础上，利用容斥可以求出无标号无根树的个数。

有标号图

有标号连通图

见前文“SET 变换”。

有标号有根树

设有标号有根树的组合类为 ，注意到树可以视为森林加一个根节点，可以写出 变形为 ，构造 则 互为复合逆。由拉格朗日反演 这指出大小为 的有标号有根树有 种。

有标号有根仙人掌

定义（边）仙人掌为：每条边至多属于一个环的图。设有根仙人掌的组合类为 。

用子仙人掌表示自身，考虑有什么结构可能和根相邻。

  • 单独的一条边：边的对面也是一个仙人掌（把对面的点置为子根）。
  • 一个环：大小为 的环额外串起 个仙人掌（把环上的点的置为子根）。此处环可以翻转但不能旋转。

定义镜像构造为 其中 是翻转置换。

显然，当 时简单地除 即可。 与根相邻的是若干边和若干环，可以写出 牛顿迭代可解出 ，具体计算较为繁琐，略去。

有标号边双连通图

连通图缩边双连通分量之后会变成一棵树。为这棵树指定一个根，拆分为子结构。

设 为有根连通图， 为有根边双连通图。用 来构建 来得到组合方程。

枚举根所在的边双大小 ，这部分是 。再考虑其他部分怎么连到根边双。每个外部连通块能且只能向根边双连一条边，少了就不连通，多了就会产生更大的边双。对于根边双的每一个点，上面都可能连接若干个外部连通块，此处对应 SET 变换。

枚举根边双大小求和，可以还原有根连通图 其中 。由扩展拉格朗日反演

有标号点双连通图

设 为有根连通图， 为（大小 的）有根点双连通图。

和边双有所不同，根可能同时被多个点双包含，这些点双的唯一交点是根。

考虑在图的根上重合（大小 的）若干个点双。对于每一个参与重合的点双，还能在除根之外的点上“重合”有根连通图，我们称这个结构为“有根重合块”。

对于一个点双大小为 的有根重合块，将点双中的所有边删除，得到 个连通块，其中根一定是孤立点，其余每个连通块是一个有根连通图。这可以认为是：从一个大小为 的有根点双开始，先去掉根，剩余的节点和有根连通图复合。

下图左侧是一个有根重合块，方形节点为点双的根，圆形节点为有根连通图的根，方形、圆形节点组成点双。下图右侧，两个有根重合块的方点（根）进行重合。

image-20250327181822760

设 为有根重合块，则 考虑用 在根处进行重合得到 ，去掉根，即 进行 SET 变换得到 ： 改写为生成函数，记 ，则 其中 。用扩展拉格朗日反演可以提取 的一项系数，进而得到 。

概率生成函数

基本概念

对于一个离散随机变量 （），定义其概率生成函数（PGF）为

或记 。

  • PGF 的性质

  • 方差的计算

根据 易证。

  • 独立随机变量的和

    是两个独立的随机变量，。

证明：

二项分布

  • 随机变量 满足参数为 的二项分布，即 ，求 的期望和方差。

Solution：

或者也可以令 以 的概率为 ， 的概率为 ，且均匀独立，则 ，故 继续计算得

  • 随机变量 满足参数为 的二项分布，求 。

Solution：

根据 ，，再利用期望和积分的线性性

其中

Tail PGF

  • 对于一个离散随机变量 （），定义其 Tail PGF 为

对于确定的 ，会产生贡献 ，可知 Tail PGF 有如下重要性质

  • 打靶问题

    每次射击有 的概率命中， 的概率不命中，重复射击直到命中为止，求所需的期望射击次数。

Solution：

（法一）记射击次数为 ，（前 次未命中，第 次命中），构造 PGF

（法二）（前 次均未命中），构造 Tail PGF

字符串、自动机与 PGF

记字符集为 ， 为 生成的全体字符串集合。 可以视为长度为 的字符串的集合。

自动机 是一个有向图，拥有一个初始点与若干终止点，其中终止点没有出边，其余点拥有 条出边，分别对应每个字符。

对于字符串 ，从初始点开始行走，第一次走 对应出边，第二次走 对应出边，以此类推……若走到终止点但字符串未走完，则称 无法识别 ，否则称 可以识别 。

定义 为 能识别的字符串集合， 为恰好走到终止点的字符串集合， 为未走到终止点的字符串集合。显然 。

  • 自动机上的随机游走

    从空串开始在自动机 上行走，每次在 中随机挑选一个字符添加到串的末尾，直到到达某个终止点为止。这一过程称作“自动机上的随机游走”。

对于一个长度为 的串，生成它的概率为 。在这样的生成规则下，为字符串集合 中的每一项配上概率，形成随机字符串 ，其长度的 PGF 为

记游走步数为 ，其 PGF 为 ，根据组合意义

考虑从 再生成一个字符，要么到达终止点，要么没到达，可得 翻译为 PGF 得 知 ，和“Tail PGF”的性质一致。

多元生成函数

常见数阵的二元生成函数

组合数

这个简洁的封闭形式将整个杨辉三角蕴含其中。

从组合意义的角度也可以得到这个生成函数，下面给出两种有趣的方法：

  • 相当于从 走到 ，每一步只能向上或向右上走的方案数。用 的次数记录横纵坐标，向上走一步对应乘 ，向右上走一步对应乘 ，根据 SEQ 变换， 的生成函数是 。

  • 一个戴帽子的人记为 ，排成一列的戴帽子的人们记为 ，用 记录人数， 记录帽子个数，则 接下来，每个人可以选择把帽子摘下或不摘下，即令 ，记 那么 对应什么呢？ 就是 个人有 个人戴帽子的方案数，即 。

第一类斯特林数

其中在 上是 EGF，在 上是 OGF。

证明：用 记录元素个数、 记录环的个数，一个有标号环的生成函数为 接下来把环组合为置换，根据有标号 SET 变换，置换的生成函数即为

对二元生成函数提取 系数可以得到一行第一类斯特林数的 OGF。

提取 系数可以得到一列第一类斯特林数的 EGF。

第二类斯特林数

其中在 上是 EGF，在 上是 OGF。

证明：用 记录元素个数， 记录无序集合（盒子）的个数，一个无序集合的生成函数为 。

接下来要得到无序集合的无序组合，根据有标号 SET 变换，第二类斯特林数的生成函数为 。

对其提取 系数，可以得到一行第二类斯特林数（的生成函数） 再提取 系数，可得 正是转幂公式二项式反演后的结果。

符号化容斥

二项式反演

二项式反演在“钦定 个的方案数”和“恰好 个的方案数”之间转换，考虑用生成函数描述这一过程。

  • 组合对象的标记

    对于有标号组合对象 ，记 ， 拥有 个标号，对应元素 。

    记 为： 的每个元素可以选择带上标记或不带标记（这些标记不影响 的大小，像是帽子），由此产生的所有 个新的组合对象。

    对于组合类 ，定义“带标记的组合类”

例如，对于 ，有

接下来，我们将用一个经典问题——错排问题——来展示标记的用法。

  • 错排问题

    对于排列 ，称满足 的位置为不动点，没有不动点的排列称为错位排列。

    记 为长为 的错排数目，求 。

Solution：

记全体排列为 ，定义 的两个子集：

  • ：带标记 不动点。

  • ：带标记 不动点。

可以发现，每个排列在 中恰出现一次，因为排列的标记方案是唯一的：标记所有不动点。所以 也可以视作全体排列的集合，只不过给所有不动点打了标记。

对于 ，若排列 有 个不动点，每个不动点都可以标记或不标记，标记方案是 。同一个排列可能出现多次，具有不同标记方式。

例如，对于排列 ：

先来研究 的结构，它的的生成可以分为两步：

  • 选定一些位置，标记它们，强制它们是不动点；

  • 其余位置无标记，任意生成。

中的每个排列，都可以划分为带标记和不带标记两部分：

  • 带标记的部分：全是不动点，对应全标记单位排列 。

  • 不带标记的部分：无限制，对应无标记自由排列 。

根据组合意义 用 表示排列长度（EGF）， 表示标记个数（OGF），可以写出 的生成函数

再考虑 是如何从 生成的：对任意一个 ，它的每个不动点都有标记，可以选择保留或摘下，这样能得到 中的所有元素。也就是 标记标记无标记

写出生成函数。原先的 中的“标记（）”，可以变为“标记（）”或“无标记（）”，相当于将 代换成 。故

至此，我们得到了排列关于 长度不动点个数 的二元生成函数 。错排（无不动点的排列）的生成函数就是 继续提取 系数得

  • 欧拉数的二元生成函数 其在 上是 EGF，在 上是 OGF。

证明：

回忆： 是长度为 的恰好有 个“升高”的排列数目。其中“升高”指一次 。长为 的排列有 个间隙，每个间隙可能对应一处“升高”或“降低”。

接下来，令标记落在间隙上，定义：

  • ：间隙带标记 升高。

  • ：间隙带标记 升高。

可以视作“标记一些间隙，强制这些间隙是升高，其余随意”。若强制 个升高，这些升高会形成恰 个“连续升高段”，满足段内元素递增，段间无要求。可以发现， 由一些“连续升高段”组成。

例如，对于未定的排列（ 代表未知的大小关系） 如果强制 那么排列会分成三个“连续升高段” 记“连续升高，且缝隙全标记的排列”（实际上，只有单位排列）为 ，则

写出生成函数，用 表示排列长度（EGF）， 表示标记数（OGF），有

再考虑 如何从 生成，此处仍有 标记标记无标记 即做代换 ，故

提取 系数，可以得到一行欧拉数 显然得到的是 次多项式，这告诉我们 的项贡献必须为 。故只需对 求出 即可，这可以用一次卷积完成。最终结果 也容易一次卷积计算。

斯特林反演

  • 染色问题

    现有一张含 个格子的纸条，每个格子皆可涂成 种颜色之一。给定正整数集合 ，定义一个染色合法当且仅当：对于任意格子，和它颜色相同的格子有 个（包括自身），则 。

    求有多少合法的染色方案。

Solution：

本例可以直接用 EGF 推导：单个颜色的 EGF 为 ，答案是 。

下面展示斯特林反演的推理方法。记

  • ：有标号非空无序集。

  • ：染色纸条。

  • ：每种颜色使用次数都在正整数集合 中的染色纸条。特殊地， 满足颜色互不相同，称作“缤纷的”染色纸条。

易知

我们的目标是求 ，首先研究 。

观察 是如何从 生成的。对于一个 ，可以将每个颜色的下标划分为一个集合，则 与“缤纷集合划分”一一对应（集合划分中，每个集合有一个颜色，且集合的颜色互不相同）。根据“子结构构造”，用有标号非空集合 替换 的元素，并继承其颜色，就能得到“缤纷集合划分”。 即将 中每个有色元素扩增为一个同色有标号集合。例如

翻译为 EGF，得 其中 的复合逆是 。

接下来，记 为有标号非空无序集，集合大小在 中。易知 类似地 这和一开始用 EGF 直接推导出的结果相同。

由于本题组合结构简单，其实也可以直接求出 。注意到 个缤纷的有标号元素方案数为 ，得

习题