符号化方法

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

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

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

无标号体系

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

A (z) = \sum_{α \in A} z^{| α |} = \sum_{n \geq 0} a_{n} z^{n}

我们约定使用同一组的字母表示同一个类对应的生成函数等，例如用 $a_{n}$ 表示 $[z^{n}] A (z)$ 即 $A (z)$ 中 $z^{n}$ 的系数，用 $A_{n}$ 表示 $A$ 中大小函数为 $n$ 的对象的集合（所以 $a_{n} = card (A_{n})$ 其中 $card$ 为基数（cardinality））。

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

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

记 $ϵ$ 为中性对象（neutral object）和 $E = {ϵ}$ 为中性类（neutral class），中性对象的大小为 $0$ ，中性类的 OGF 为 $E (z) = 1$ 。
记 $\circ$ 或 $∙$ 为原子对象（atom object）和 $Z_{\circ} = {\circ}$ 或 $Z_{∙} = {∙}$ 或简写为 $Z$ 为原子类（atom class），原子对象的大小为 $1$ ，原子类的 OGF 为 $Z (z) = z$ 。

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

我们有

A ≅ E \times A ≅ A \times E

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

集合的（不相交）并构造

对于类 $A$ 和 $B$ 的并记为

A + B = (E_{1} \times A) + (E_{2} \times B)

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

对应 OGF 为

A (z) + B (z)

考虑

A (z) + B (z) = \sum_{α \in A} z^{| α |} + \sum_{β \in B} z^{| β |} = \sum_{n \geq 0} (a_{n} + b_{n}) z^{n}

对应形式幂级数的加法。

集合的笛卡尔积构造

对于类 $A$ 和 $B$ 的笛卡尔积记为

A \times B = {(α, β) ∣ α \in A, β \in B}

对应 OGF 为

A (z) \cdot B (z)

我们定义 $(α, β)$ 的大小为其组成部分的大小之和，那么显然也有

γ = (α_{1}, α_{2}, \dots, α_{n}) ⟹ | γ | = | α_{1} | + | α_{2} | + \dots + | α_{n} |

所以

A (z) \cdot B (z) = (\sum_{α \in A} z^{| α |}) (\sum_{β \in B} z^{| β |}) = \sum_{(α, β) \in (A \times B)} z^{| α | + | β |} = \sum_{n \geq 0} \sum_{i + j = n} a_{i} b_{j} z^{n}

对应形式幂级数的乘法。

集合的 Sequence 构造

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

例

\begin{aligned} SEQ ({a}) & = {ϵ} + {a} + {(a, a)} + {(a, a, a)} + \dots \\ SEQ ({a, b}) & = {ϵ} + {a, b} + {(a, b)} + {(b, a)} + {(a, a)} + {(b, b)} \\ + {(a, b, a)} + {(a, b, b)} + {(a, a, b)} \\ + {(b, b, a)} + {(b, a, b)} + {(b, b, b)} + {(a, a, a)} + {(b, a, a)} \\ + \dots \end{aligned}

可以看到 ${(a, b)}, {(b, a)}$ 这样组成部分的顺序不同的元素被生成了，可以认为 Sequence 构造生成了有序的组合。

我们定义

SEQ (A) = E + A + (A \times A) + (A \times A \times A) + \dots

且要求 $A_{0} = \emptyset$ ，也就是 $A$ 中没有大小为 $0$ 的对象。

对应 OGF 为

Q (A (z)) = 1 + A (z) + A (z)^{2} + A (z)^{3} + \dots = \frac{1}{1 - A (z)}

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

例：有序有根树（ordered rooted tree）

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

T = {∙} \times SEQ (T)

对应 OGF 为

T (z) = \frac{z}{1 - T (z)}

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

集合的 Multiset 构造

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

例

\begin{aligned} MSET ({a}) & = {ϵ} + {a} + {(a, a)} + {(a, a, a)} + \dots \\ MSET ({a, b}) & = {ϵ} + {a} + {(a, a)} + {(a, a, a)} + \dots \\ + {b} + {(a, b)} + {(a, a, b)} + \dots \\ + {(b, b)} + {(a, b, b)} + {(a, a, b, b)} + \dots \\ + \dots \end{aligned}

注意到 ${(b, a)}, {(a, b, a)}$ 在 $SEQ ({a, b})$ 中出现，但在 $MSET ({a, b})$ 没有出现，可以认为 Multiset 生成了无序的组合。

我们定义其递推式为

MSET ({α_{0}, α_{1}, \dots, α_{n}}) = MSET ({α_{0}, α_{1}, \dots, α_{n - 1}}) \times SEQ ({α_{n}})

即

MSET (A) = \prod_{α \in A} SEQ ({α})

且要求 $A_{0} = \emptyset$ 。或者也可以给出等价的

MSET (A) = SEQ (A) / R

其中 $R$ 为等价关系，我们说 $(α_{1}, \dots, α_{n}) R (β_{1}, \dots, β_{n})$ 当且仅当存在任一置换 $σ$ 对于所有 $j$ 满足 $β_{j} = α_{σ (j)}$ 。

对应 OGF 为

Exp (A (z)) = \prod_{α \in A} {(1 - z^{| α |})}^{- 1} = \prod_{n \geq 1} {(1 - z^{n})}^{- a_{n}}

注意到

\ln (1 + z) = \frac{z}{1} - \frac{z^{2}}{2} + \frac{z^{3}}{3} - \dots = \sum_{n \geq 1} \frac{(- 1)^{n - 1} z^{n}}{n}

且 $A (z) = \exp (\ln (A (z)))$ 所以

\begin{aligned} Exp (A (z)) & = \exp (\sum_{n \geq 1} - a_{n} \cdot \ln (1 - z^{n})) \\ = \exp (\sum_{n \geq 1} - a_{n} \cdot \sum_{m \geq 1} \frac{- z^{n m}}{m}) \\ = \exp (\frac{A (z)}{1} + \frac{A (z^{2})}{2} + \frac{A (z^{3})}{3} + \dots) \end{aligned}

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

例题 LOJ 6268. 分拆数

题意：令 $f (n)$ 表示将 $n$ 进行分拆的方案数，求 $f (1), f (2), \dots, f (10^{5})$ 对 $998244353$ 取模的值。

解：设全体正整数类为 $I$ ，那么 $I = {SEQ}_{\geq 1} (Z) = Z \times SEQ (Z)$ （下标 $\geq 1$ 为有限制的构造，见后文）。所求即

MSET (I)

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

例题洛谷 P4389 付公主的背包

题意：给出 $n$ 种体积分别为 $v_{1}, \dots, v_{n}$ 的商品和正整数 $m$ ，求体积为 $1, 2, \dots, m$ 的背包装满的方案数（商品数量不限，有同体积的不同种商品）对 $998244353$ 取模的值。约定 $1 \leq n, m \leq 10^{5}$ 且 $1 \leq v_{i} \leq m$ 。

解：设商品的组合类为 $A$ ，所求即 $MSET (A)$ 对应 OGF 的系数。

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

题意：求出 $n$ 个节点的无标号无根树的个数对 $998244353$ 取模的值。约定 $1 \leq n \leq 2 \times 10^{5}$ 。

解：设无标号有根树的组合类为 $T$ ，那么

T = {∙} \times MSET (T)

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

T (z) - \frac{1}{2} T^{2} (z) + \frac{1}{2} T (z^{2})

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

集合的 Powerset 构造

Powerset 构造生成了所有子集。

例

\begin{aligned} PSET ({a}) & = {ϵ} + {a} \\ PSET ({a, b}) & = {ϵ} + {a} + {b} + {(a, b)} \\ PSET ({a, b, c}) & = {ϵ} + {a} + {b} + {(a, b)} + {c} + {(a, c)} + {(b, c)} + {(a, b, c)} \end{aligned}

我们定义其递推式为

PSET ({α_{0}, α_{1}, \dots, α_{n}}) = PSET ({α_{0}, α_{1}, \dots, α_{n - 1}}) \times ({ϵ} + {α_{n}})

即

PSET (A) ≅ \prod_{α \in A} ({ϵ} + {α})

且要求 $A_{0} = \emptyset$ 。

对应 OGF 为

\begin{aligned} \overset{―}{Exp} (A (z)) & = \prod_{α \in A} (1 + z^{| α |}) = \prod_{n \geq 1} {(1 + z^{n})}^{a_{n}} \\ = \exp (\sum_{n \geq 1} a_{n} \cdot \ln (1 + z^{n})) \\ = \exp (\sum_{n \geq 1} a_{n} \cdot \sum_{m \geq 1} \frac{(- 1)^{m - 1} z^{n m}}{m}) \\ = \exp (\frac{A (z)}{1} - \frac{A (z^{2})}{2} + \frac{A (z^{3})}{3} - \dots) \end{aligned}

其中 $\overset{―}{Exp}$ 为 Pólya 指数·改。

容易发现 $PSET (A) \subset MSET (A)$ 。

集合的 Cycle 构造

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

我们定义为

CYC (A) = (SEQ (A) ∖ {ϵ}) / S

其中 $S$ 为等价关系，我们说 $(α_{1}, \dots, α_{n}) S (β_{1}, \dots, β_{n})$ 当且仅当存在任一循环移位 $τ$ 对于所有 $j$ 都满足 $β_{j} = α_{τ (j)}$ 。

例

为了简便我们令 $a, b$ 均为大小为 $1$ 的字符，这里仅列举大小为 $3$ 和 $4$ 的字符串：

CYC ({a, b})_{3} = {aaa} + {aab} + {abb} + {bbb}

其中 $aab S baa S aba$ 只保留其一，同样的 $abb S bab S bba$ 只保留其一。

CYC ({a, b})_{4} = {aaaa} + {aaab} + {aabb} + {abbb} + {bbbb} + {abab}

其中 $aaab S baaa S abaa S aaba$ ， $aabb S baab S bbaa S abba$ ， $abbb S babb S bbab S bbba$ 和 $abab S baba$ 。

对应 OGF 为

Log (A (z)) = \sum_{n \geq 1} \frac{φ (n)}{n} \ln \frac{1}{1 - A (z^{n})}

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

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

有限制的构造

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

{SEQ}_{= k} (B), {SEQ}_{\geq k} (B), {SEQ}_{1. . k} (B)

其中 ${SEQ}_{= k} (B)$ 也常简写为 ${SEQ}_{k} (B)$ ， ${SEQ}_{1. . k} (B)$ 表示在区间 $[1. . k]$ 上。

令 $K$ 为任意上述 $SEQ, PSET, MSET, CYC$ 之一，以及

A = K_{k} (B)

即我们需要对于 $α \in A$ 有

α = {(β_{1}, β_{2}, \dots, β_{k}) ∣ β \in B}

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

令

A_{n, k} = card {α \in A ∣ | α | = n, χ (α) = k}

那么

A (z, u) = \sum_{n, k} A_{n, k} u^{k} z^{n} = \sum_{α \in A} z^{| α |} u^{χ (α)}

然后我们只要提取出 $u^{k}$ 的系数即可获得对应表达式，例如 $A = {SEQ}_{k} (B)$ 可直接导出

\begin{aligned} A (z, u) = \sum_{k \geq 0} u^{k} B (z)^{k} = \frac{1}{1 - u B (z)} \\ ⟹ & A (z) = B (z)^{k} \end{aligned}

显然也有

A = {SEQ}_{\geq k} (B) ⟹ A (z) = \frac{B (z)^{k}}{1 - B (z)}

而对于 ${MSET}_{k} (B)$ 和 ${PSET}_{k} (B)$ 已经有

\begin{aligned} A (z, u) = \prod_{n} {(1 - u z^{n})}^{- b_{n}} \\ ⟹ & A (z) = [u^{k}] \exp (\frac{u}{1} B (z) + \frac{u^{2}}{2} B (z^{2}) + \frac{u^{3}}{3} B (z^{3}) + \dots) \end{aligned}

和

\begin{aligned} A (z, u) = \prod_{n} {(1 + u z^{n})}^{b_{n}} \\ ⟹ & A (z) = [u^{k}] \exp (\frac{u}{1} B (z) - \frac{u^{2}}{2} B (z^{2}) + \frac{u^{3}}{3} B (z^{3}) - \dots) \end{aligned}

对于 ${CYC}_{k} (B)$ 同理。

使用上式计算

{MSET}_{3} (B)

和

{MSET}_{4} (B)

对应 OGF

尝试计算 $A = {MSET}_{3} (B)$ 为

\begin{aligned} [u^{3}] A (z, u) & = \frac{1}{0!} ([u^{3}] 1) + \frac{1}{1!} ([u^{3}] (\frac{u}{1} B (z) + \frac{u^{2}}{2} B (z^{2}) + \frac{u^{3}}{3} B (z^{3}) + \dots)) \\ + \frac{1}{2!} ([u^{3}] {(\frac{u}{1} B (z) + \frac{u^{2}}{2} B (z^{2}) + \dots)}^{2}) \\ + \frac{1}{3!} ([u^{3}] {(\frac{u}{1} B (z) + \dots)}^{3}) \\ = \frac{B (z)^{3}}{6} + \frac{B (z) B (z^{2})}{2} + \frac{B (z)^{3}}{3} \end{aligned}

尝试计算 $A = {MSET}_{4} (B)$ 为

\begin{aligned} [u^{4}] A (z, u) & = \frac{1}{0!} ([u^{4}] 1) + \frac{1}{1!} ([u^{4}] (\frac{u}{1} B (z) + \frac{u^{2}}{2} B (z^{2}) + \frac{u^{3}}{3} B (z^{3}) + \frac{u^{4}}{4} B (z^{4}) + \dots)) \\ + \frac{1}{2!} ([u^{4}] {(\frac{u}{1} B (z) + \frac{u^{2}}{2} B (z^{2}) + \frac{u^{3}}{3} B (z^{3}) + \dots)}^{2}) \\ + \frac{1}{3!} ([u^{4}] {(\frac{u}{1} B (z) + \frac{u^{2}}{2} B (z^{2}) + \dots)}^{3}) \\ + \frac{1}{4!} ([u^{4}] {(\frac{u}{1} B (z) + \dots)}^{4}) \\ = \frac{B (z^{4})}{4} + \frac{1}{2!} (\frac{B (z^{2})^{2}}{4} + \frac{2 B (z) B (z^{3})}{3}) + \frac{1}{3!} (\frac{3 B (z)^{2} B (z^{2})}{2}) + \frac{B (z)^{4}}{4!} \\ = \frac{B (z)^{4}}{24} + \frac{B (z)^{2} B (z^{2})}{4} + \frac{B (z) B (z^{3})}{3} + \frac{B (z^{2})^{2}}{8} + \frac{B (z^{4})}{4} \end{aligned}

我们发现 $A = K_{k} (B)$ 中 $A (z)$ 是关于 $B (z), B (z^{2}), \dots, B (z^{k})$ 的一个表达式。

需要注意的是对于有限制的构造 $K_{k} (B)$ 并没有要求 $B_{0} = \emptyset$ 。

常用有限制的构造

\begin{aligned} {PSET}_{2} (A) & : \frac{A (z)^{2}}{2} - \frac{A (z^{2})}{2} \\ {MSET}_{2} (A) & : \frac{A (z)^{2}}{2} + \frac{A (z^{2})}{2} \\ {CYC}_{2} (A) & : \frac{A (z)^{2}}{2} + \frac{A (z^{2})}{2} \end{aligned}

\begin{aligned} {PSET}_{3} (A) & : \frac{A (z)^{3}}{6} - \frac{A (z) A (z^{2})}{2} + \frac{A (z^{3})}{3} \\ {MSET}_{3} (A) & : \frac{A (z)^{3}}{6} + \frac{A (z) A (z^{2})}{2} + \frac{A (z^{3})}{3} \\ {CYC}_{3} (A) & : \frac{A (z)^{3}}{3} + \frac{2 A (z^{3})}{3} \end{aligned}

\begin{aligned} {PSET}_{4} (A) & : \frac{A (z)^{4}}{24} - \frac{A (z)^{2} A (z^{2})}{4} + \frac{A (z) A (z^{3})}{3} + \frac{A (z^{2})^{2}}{8} - \frac{A (z^{4})}{4} \\ {MSET}_{4} (A) & : \frac{A (z)^{4}}{24} + \frac{A (z)^{2} A (z^{2})}{4} + \frac{A (z) A (z^{3})}{3} + \frac{A (z^{2})^{2}}{8} + \frac{A (z^{4})}{4} \\ {CYC}_{4} (A) & : \frac{A (z)^{4}}{4} + \frac{A (z^{2})^{2}}{4} + \frac{A (z^{4})}{2} \end{aligned}

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

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

题意：求出 $n$ 个节点的有根且根节点度数不超过 $3$ ，其余节点度数不超过 $4$ 的无序树的个数对 $998244353$ 取模的值。约定 $1 \leq n \leq 10^{5}$ 。

解：设组合类为 $T$ 那么

T = {∙} \times {MSET}_{0, 1, 2, 3} (T)

或令组合类 $\hat{T} = T + {ϵ}$ 那么

\hat{T} = {ϵ} + {∙} \times {MSET}_{3} (\hat{T})

可得到相同的结果。

参考文献

Philippe Flajolet and Robert Sedgewick.Analytic Combinatorics.

本页面最近更新：2023/2/18 07:57:07，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Great-designer, hly1204, myeeye, shuzhouliu
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用