符号化方法

技术分享 3年前 (2023-02-01) 0 999+

解析组合试图从一个较为机械化的方式帮助我们将组合计数问题从模型直接转为生成函数。

—— $text{EntropyIncreaser}$

解析组合为我们提供了一套能处理一系列组合结构计数和渐进估计的方法，分为解析和组合两个部分。
解析的部分主要讨论了如何近似生成函数的系数，而组合的部分则着眼于操作组合结构以便计数。符号化方法就是组合部分中操作组合结构的一种机械方法，通过描述组合结构来声明对应的生成函数。通过这种方式，我们就可以跳过转移方程，直接写出生成函数，也能够得到关于生成函数和组合意义的联系的更深刻理解。

阅读下文可能需要有基础的生成函数知识。也许是前置知识。

注意本文内容可能有疏漏或错误，如果读者发现敬请在评论区指出不足。

(1.) 无标号体系

(1.1) 记号与定义

组合对象是满足某一性质的可数对象，例如二叉树、烯烃或字符串。组合类是一系列组合对象组成的可数集合。
下面将采用美术花体（mathcal）大写字母表示一个组合类。

每个组合类 (mathcal A) 都定义了一个大小函数 (f: mathcal Ato mathbb N)，满足对任何 (kin mathbb N) 只有有限个组合对象 (ain mathcal A) 满足 (f(a) = k)。(f(a)) 表示了组合对象 (a) 的固有属性，可能是树高、节点数或串长等。常记 (f(a)) 为 (lvert arvert)（在某些需要指明组合类的场合下记作 (lvert a rvert_{mathcal A})）。
我们将 (ain mathcal A text{ s.t. } lvert a rvert = n) 的全体记作 (mathcal A_n)，并以此构造一个计数序列 (A)，满足 (A[n] = lvert mathcal A_nrvert)。
两个组合类 (mathcal A, mathcal B) 在组合意义上同构记作 (mathcal A = mathcal B) 或 (mathcal A cong mathcal B)，但仅在 (mathcal A) 和 (mathcal B) 不同构时才用后一种记号。

我们在描述组合对象时只会关注我们需要的单一性质，这种抽象有助于我们理解下文中将不同对象组合为新的对象的操作。总的来说，我们忽视组合对象除了“大小”外的所有信息，这样很多组合操作都可以被简单地映射在“并列”操作上。

一个组合类 (mathcal A) 的 (text{OGF}) 可以用它对应的计数序列 (A) 的 (text{OGF}) 表示，即为一个形式幂级数

[A(z) = sum_{ige 0} A[i] z^i ]

它也可以被等价地写作

[A(z) = sum_{ain mathcal A} z^{lvert a rvert} ]

我们称 (z^{lvert a rvert}) 为 (a) 的幂表示，这里的 (z) 仍然只是占位元。

由以上内容不难验证组合类的笛卡尔积和 (text{OGF}) 的乘法 (times) 同构，集合不交并和 (text{OGF}) 的加法 (+) 同构（处理了重复元素的加法会在下方重新定义）。
下面对集合的笛卡尔积也记作 (times)，集合并也记作 (+)。

组合类都是由一些更本质的组合类构造出来的；一个构造是从一组组合类映射到一个组合类的函数。
当我们说一个构造可以被翻译为生成函数运算时，我们想要表达的就是这种组合类间的映射能和生成函数间的运算对应。一个经典的例子是 (exp) 的组合意义；下文中还会有更多类似的例子。

下文中需要对某些表性相似的元素加以合并，因此在这里引入等价关系和等价类的定义。

对于组合类 (mathcal A)，设其中任意对象都是 (mathcal B) 中某些对象的组合。我们定义 (ain mathcal A) 对 (mathcal B) 的拆分为 (a = (b_1, b_2, dots, b_m), forall b_i in mathcal B)，这拆分一般应当是唯一的。记 (a) 在 (mathcal B) 上的容为 (text{cap}_{mathcal B}(a) = m)，即拆分中的元素个数。

我们定义一个等价关系是一个置换群列，用加粗大写字母（textbf）表示。假设 (textbf G) 是一个置换群列，则可以记 (textbf G = {G_0, G_1, G_2,dots})，其中 (G_k) 是一个置换群，满足任意 (gin G_k) 都是一个大小为 (k) 的元素上的置换。若一个等价关系 (textbf G) 是针对组合类 (mathcal A) 中元素对 (mathcal B) 的拆分定义的，则称 (textbf G) 以 (mathcal B) 为拆分集，记作 (textbf G_{mathcal B})。

我们定义 (a_1, a_2) 对 (mathcal B) 的拆分在 (textbf G) 上等价（本质相同）当且仅当

(text{cap}_{mathcal B}(a_1) = text{cap}_{mathcal B}(a_2))；
(exists gin G_{text{cap}_{mathcal B}(a_1)}, g(a_1) = a_2)。

注意这里 (g) 的作用是将 (a_1) 的拆分重排。
下面常将两个拆分 ((a_1, a_2, dots a_n)) 和 ((b_1, b_2, dots, b_n)) 在 (textbf G) 上等价记作 ((a_1, a_2, dots a_n)textbf G(b_1, b_2, dots, b_n))。下文中也会以下标变换的方式说明对应的 (gin G_n) 的形式。

对于组合类 (mathcal A) 和等价关系 (textbf G)，取一个 (mathcal A) 的子集 (mathcal S)，若 (mathcal S) 中任意两个对象等价，且任意 (mathcal S) 中对象和 (complement_{mathcal A}mathcal S) 中对象不等价，则我们称 (mathcal S) 是 (textbf G) 下的等价类。常记 (lvert mathcal Srvert) 为等价类中一个元素的大小。需要注意的是，一般等价类中任意组合对象大小相等。

对于组合类 (mathcal A) 和等价关系 (textbf G_{mathcal B})，定义 (mathcal A / textbf G_{mathcal B}) 得到了一个新的组合类，满足任意原等价类在新的组合类中有且仅有一个元素作为代表；这里常取在某一性质（例如字典序）下最小元素。有时也定义新的组合类中的对象是原组合类中的等价类，即新组合类是“组合类的组合类”。

在下面对组合类的构造过程中，新组合类的对象常对原组合类进行拆分，因此在语义明显时不声明原组合类为等价关系的拆分集。

(1.2) 基础组合类

下面引入两种特殊的组合对象和对应的组合类。

我们记 (epsilon) 为中性对象（neutral object），对应的组合类记作 (mathcal E = {epsilon })，称作中性类（neutral class）。
恒有 (lvert epsilon rvert = 0)，因此有中性类的 (text{OGF}) (E(z) = 1)。
需要注意的是，两个中性对象 (epsilon_1, epsilon_2) 可能不同。记一个下标为 (k) 的中性对象 (epsilon_k) 对应的类为 (mathcal E_k)。
我们有

[mathcal A cong mathcal Etimes mathcal A cong mathcal Atimes mathcal E ]

对于任意组合类 (mathcal A)，规定 (mathcal A^0 = mathcal E)。但是由于组合意义，(mathcal E) 不能视作笛卡尔积的单位元。

定义了中性对象后，我们就可以定义不需要考虑交集的集合并了。由于集合论中需要满足集合内无重合元素，我们可以对两个类分别乘上不同的中性类，这样两个类中可能相同的对象在并集中也彼此不同。
我们定义两个类 (mathcal A, mathcal B) 的集合并 (mathcal A + mathcal B) 为

[(mathcal E_1 times mathcal A) cup (mathcal E_2 times mathcal B) ]

其中 (cup) 为集合的不交并。

我们记 (bullet) 为原子对象（atom object），对应的组合类记作 (mathcal Z = {bullet })，称作原子类（atom class）。
恒有 (lvert bullet rvert = 1)，因此有中性类的 (text{OGF}) (Z(z) = z)。
原子对象常用于合并数个组合对象，经典例子是作为树的根出现。

(1.3) 例题

(textbf{例 1})：01 串

我们如何求得长度为 (n) 的 01 串的个数？

设 01 串的组合类为 (mathcal S)，我们要求的就是 (lvertmathcal S_nrvert)。可以写出

[mathcal S = { epsilon, mathtt{0}, mathtt{1}, mathtt{00}, mathtt{01}, mathtt{10}, mathtt{11}, mathtt{000},dots } ]

对于某个 01 串，其要么为空串，要么是 (mathtt{0},mathtt{1}) 接在另一个 01 串前面。可以写出

[mathcal S = mathcal E + { mathtt{0}, mathtt{1} }times mathcal S ]

翻译成生成函数就是 (S(z) = 1 + (z + z) S(z))，也就能得到 (S(z) = dfrac{1}{1 - 2z})。答案即为 ([z^n]S(z) = 2^n)。

(textbf{例 2})：卡特兰数

我们如何构造长度为 (n) 的生成函数？

卡特兰数有一个很经典的组合意义：(Cat(n)) 是 (n) 个点的二叉树个数。

对于一棵二叉树，它要么为空，要么形如 (左子树-根-右子树)。根可以视作 (bullet)，两侧则又是二叉树。
假设二叉树的组合类为 (mathcal C)，可以写出

[mathcal C = mathcal E + mathcal C times mathcal Z times mathcal C ]

翻译成生成函数就是 (C(z) = 1 + zC(z)^2)，这和我们先前得到的形式相同。

(2.) 经典的无标号构造

(2.1) 集合的 (text{Sequence}) 构造

(text{Sequence}) 构造生成了所有可能的有序组合。

我们定义

[text{SEQ}(mathcal A) = mathcal E + mathcal A + left(mathcal A times mathcal Aright) + left(mathcal A times mathcal A times mathcal Aright) + cdots ]

且要求 (mathcal A_0 = varnothing)，也就是 (mathcal A) 中没有大小为 (0) 的对象。我们还可以将这构造生成的组合类写作

[text{SEQ}(mathcal A) = left{left(beta_1, beta_2, dots, beta_kright) | kge 0, beta_i in mathcal Aright} ]

这映射翻译为生成函数即为

[Q(A(z)) = 1 + A(z) + A^2(z) + A^3(z) + cdots = frac{1}{1 - A(z)} ]

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

(textbf{例 1})：写出 ({text{a}, text{b}}) 的 (text{Sequence}) 构造：

[begin{aligned} &text{SEQ}(left{text{a}, text{b}right}) \ = & quad {epsilon} + {text{a}} + {text{b}} + {text{a} text{b}} + {text{b} text{a}} \ & + {text{aaa}} + {text{aab}} + {text{aba}} + {text{abb}} \ & + {text{baa}} + {text{bab}} + {text{bba}} + {text{bbb}} \ & + cdots end{aligned}]

(textbf{例 2})：有序有根树计数

我们可以使用 (text{Sequence}) 构造来定义有序有根树（不同儿子之间的顺序有意义的有根树）的计数。

设对应的组合类是 (mathcal T)，我们可以用一个原子对象和自身的 (text{Sequence}) 描述自身，也就是

[mathcal T = mathcal Ztimes text{SEQ}(mathcal T) ]

翻译为生成函数就是

[T(z) = frac{z}{1 - T(z)} ]

从这里也可以看出，(T(z) = dfrac{1 - sqrt{1 - 4z}}{2})，因此大小为 (n) 的有序有根树的大小为移位的卡特兰数。

(2.2) 集合的 (text{Multiset}) 构造

(text{Multiset}) 构造生成了所有可能的组合，但是不区分对象内部的元素的顺序。

我们仍然可以使用 (text{Sequence}) 构造描述 (text{Multiset}) 构造，但是由于顺序原因，我们可以递推解决，每次只拿出一个元素作 (text{Sequence}) 构造。假设 (mathcal A = left{alpha_0, alpha_1, dots, alpha_k right})，则可以递推地作 (text{Multiset}) 构造。

[text{MSET}(left{alpha_0, alpha_1, dots, alpha_k right}) = text{MSET}(left{alpha_0, alpha_1, dots, alpha_{k - 1} right})times text{SEQ}(left{alpha_kright}) ]

即

[text{MSET}(mathcal A) = prod_{alpha in mathcal A} text{SEQ}({alpha}) ]

且要求 (mathcal A_0 = varnothing)。可以得到等价的

[text{MSET}(mathcal A) = text{SEQ}(mathcal A) / textbf R ]

其中 ((a_1, a_2, dots, a_n)textbf{R}(b_1, b_2, dots, b_n)) 当且仅当存在一个置换 (sigma)，对于任意 (j) 满足 (b_j = a_{sigma(j)})。

翻译为生成函数就是

[text{Exp}(A(z)) = prod_{alpha in mathcal A} left( 1 - z^{lvertalpharvert} right)^{-1} = prod_{ige 1} (1 - z^i)^{- A[i]} ]

作 (ln - exp) 可以得到

[begin{aligned} &text{Exp}(A(z)) \ = & expleft( sum_{ige 1} - A[i] ln(1 - z^i) right) \ = & expleft( sum_{ige 1} - A[i] sum_{jge 1} frac{-z^{ij}}{j} right) \ = & expleft( sum_{jge 1} frac{1}{j} sum_{ige 1} A[i] (z^{j})^{i} right) \ = & expleft( sum_{jge 1} frac{A(z^j)}{j} right) end{aligned}]

其中 (text{Exp}) 被称作为 Pólya 指数，又称 Euler 变换。

(textbf{例 1})：整数的分拆

对每个 (1le i le 10^5) 求 (f(i))，其中 (f(k)) 是将 (k) 进行分拆的方案数。

设全体正整数类为 (mathcal I)，可以发现

[mathcal I = text{SEQ}_{ge 1}(mathcal Z) = mathcal Z times text{SEQ}(mathcal Z) ]

(text{SEQ}_{ge 1}) 是有限制的构造，在下方讲到。当然求上面的东西对答案没啥帮助，我们可以直接构造 (I(z) = sum_{ige 1} z^i)。
所求的就是 (text{MSET}(mathcal I))。

(textbf{例 2})：无标号无根树计数

我们能否对无标号无根树的计数构造生成函数？

假设无标号有根树的组合类是 (mathcal T)，则可以写出

[mathcal T = mathcal Z times text{MSET}(mathcal T) ]

也就是

[T(z) = ztext{Exp}(A(z)) ]

对于无根的情况，论文 The Number of Trees, Richard Otter 说明了无根树的 (text{OGF}) 是

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

这点也可以通过对奇偶次项系数进行不同的讨论得到。

(textbf{例 3})：Pólya 指数的逆变换

我们能否根据 (text{Exp}) 的结构得到它的逆变换（不考虑常数项）？

记给定幂级数为 (F(z))。我们需要求的就是一个序列 (A)，满足

[F(z) = prod_{i ge 1} (1 - z^i)^{-A[i]} ]

两边取对数。得到

[begin{aligned} ln F(z) & = sum_{i ge 1} - A[i] ln(1 - z^i) \ & = sum_{i ge 1} A[i] sum_{jge 1} frac{z^{ij}}{j} \ & = sum_{Tge 1} z^{T} sum_{d | T} frac{d}{T} A[d] end{aligned}]

记 (ln F(z)) 为 (f)，可以发现

[f[T] = frac{1}{T}sum_{d|T} d A[d] ]

作莫比乌斯反演得到

[A[T] = frac{1}{T} sum_{d|T} df[d] timesmuleft(frac{T}{d}right) ]

这就是逆运算的构造。

(2.3) 集合的 (text{Powerset}) 构造

(text{Powerset}) 构造生成了所有可能的子集。

可以发现，对于每个元素我们都可以选或不选，这会导出两类不同的子集。因此我们可以递归地定义 (text{PSET}) 构造：

[text{PSET}(left{alpha_0, alpha_1, dots, alpha_k right}) = text{PSET}(left{alpha_0, alpha_1, dots, alpha_{k - 1} right})times (mathcal E + left{alpha_kright}) ]

可以写作

[text{PSET}(mathcal A) cong prod_{alpha in mathcal A} (mathcal E + {alpha}) ]

要求 (mathcal A_0 = varnothing)。

容易发现 (text{PSET}(mathcal A)subset text{MSET}(mathcal A))，因为 (mathcal E + {alpha} = text{SEQ}_{kle 1}({alpha}))。

翻译为生成函数就是

[overline{text{Exp}}(A(z)) = prod_{ige 1} (1 - z^i)^{A[i]} = expleft( sum_{i ge 1} (-1)^{i + 1} frac{A(z^i)}{i} right) ]

(2.4) 集合的 (text{Cycle}) 构造

(text{Cycle}) 构造生成了所有可能的组合，但是不区分仅轮换不同的组合。

我们定义这个构造为

[text{CYC}(mathcal A) = left(text{SEQ}(mathcal A) backslash mathcal Eright) / textbf S ]

其中 (textbf S) 为等价关系，((a_1, a_2, dots a_n) textbf S(b_1, b_2, dots, b_n)) 当且仅当存在循环移位 (tau) 使得对于任意 (j) 有 (b_j = a_{tau(j)})。

翻译为生成函数是

[text{Log}(A(z)) = sum_{kge 1} frac{varphi(k)}{k} ln frac{1}{1 - A(z^k)} ]

(text{Log}) 被称作为 Pólya 对数。公式的证明可以参见 The Cycle Construction, P. Flajolet and M. Soria，这里不再展开。采用群论相关知识我们也可以获得相同的结果。

(textbf{例 1})：列举 (text{CYC}({text{a}, text{b}})) 中长度为 (4) 的对象。

它们分别为

[text{aaaa}, text{aaab}, text{aabb}, text{abbb}, text{bbbb}, text{abab} ]

由于 (text{aaab}textbf Stext{aaba}textbf Stext{abaa}textbf Stext{baaa}, text{aabb}textbf Stext{abba}textbf Stext{bbaa}textbf Stext{baab}, text{abbb}textbf Stext{bbba}textbf Stext{bbab}textbf Stext{babb}, text{abab}textbf Stext{baba})，这几个等价类都只有一个元素出现在 (text{CYC}({text{a}, text{b}})) 中。

这里采用字典序最小的字符串作为代表。

(2.5) 有限制的构造

对于上述构造，我们并没有限制每个对象组成部分的个数。
这里以 (text{SEQ}) 构造为例。我们若在 (text{SEQ}) 的下标加上作用于整数的谓词用于约束其组成部分的个数，如 (text{SEQ}_{= k}, text{SEQ}_{ge k}, text{SEQ}_{in [1, k]})，则表示构造出的等价类中每个对象的拆分中相同元素需要被下标上对应的谓词限制。常简写 (text{SEQ}_{= k}) 为 (text{SEQ}_{k})。

令一个构造 (text{CONS}) 为上述构造中的一种，并设 (mathcal A = text{CONS}_k(mathcal B))，则我们需要对 (forall alpha in mathcal A) 有 (alpha = left{(beta_1, beta_2, dots, beta_k) mid forall beta_i in mathcal B right})。

这种构造我们在先前已经充分接触过了，其翻译到生成函数上就是用新占位元来标识组成部分的个数。
组合意义上，我们定义 (chi) 函数作用于一个元素上标识其组成部分的个数，也就是它需要被对应的逻辑谓词限制。用在上面的例子上就是 (chi(alpha) = k)。

延续先前的记号，令

[mathcal A_{n, k} = leftlvert left{ alpha in mathcal A mid lvertalpharvert = n, chi(alpha) = k right} rightrvert ]

翻译为生成函数即为

[A(z, t) = sum_{nge 0} sum_{kge 0} mathcal A_{n, k} z^n t^k = sum_{alpha in mathcal A} z^{lvert alpha rvert} t^{chi(alpha)} ]

我们只需要提取 (t^k) 项系数即可得到对应的表达式。对应 (text{SEQ}_k) 就能得到

[A(z, t) = sum_{kge 0} B(z)^k t^z = frac{1}{1 - tB(z)} ]

也就是 (A(z) = B(z)^k)。同样能得到 (text{SEQ}_{ge k}(mathcal B)) 能引出 (A(z) = dfrac{B(z)^k}{1 - B(z)})。

对于 (text{MSET}_k) 有

[A(z, t) = prod_{nge 0} (1 - tz^n)^{- B[n]} ]

这个得提取系数，得到

[A(z) = [t^k] exp left( sum_{ige 1} frac{t^iB(z^i)}{i} right) = sum_{ige 0} frac{1}{i!} [t^k]left( sum_{jge 1} frac{t^j B(z^j)}{j} right)^i ]

对于有限制的构造，没有要求 (mathcal B_0 = varnothing)。

常用的有限制构造

[begin{aligned} text{PSET}_2(mathcal A) &= frac{A(z)^2}{2} - frac{A(z^2)}{2} \ text{MSET}_2(mathcal A) &= frac{A(z)^2}{2} + frac{A(z^2)}{2} \ text{CYC}_2(mathcal A) &= frac{A(z)^2}{2} + frac{A(z^2)}{2} end{aligned}]

[begin{aligned} text{PSET}_3(mathcal A) &= frac{A(z)^3}{6} - frac{A(z)A(z^2)}{2} + frac{A(z^3)}{3} \ text{MSET}_3(mathcal A) &= frac{A(z)^3}{6} + frac{A(z)A(z^2)}{2} + frac{A(z^3)}{3} \ text{CYC}_3(mathcal A) &= frac{A(z)^3}{3} + frac{2A(z^3)}{3} end{aligned}]

[begin{aligned} text{PSET}_4(mathcal A) &= frac{A(z)^4}{24} - frac{A(z)^2A(z^2)}{4} + frac{A(z)A(z^3)}{3} + frac{A(z^2)^2}{8} - frac{A(z^4)}{4} \ text{MSET}_4(mathcal A) &= frac{A(z)^4}{24} + frac{A(z)^2A(z^2)}{4} + frac{A(z)A(z^3)}{3} + frac{A(z^2)^2}{8} + frac{A(z^4)}{4} \ text{CYC}_4(mathcal A) &= frac{A(z)^4}{4} + frac{A(z^2)^2}{4} + frac{A(z^4)}{2} end{aligned}]

上面的计算方法比较麻烦，我们也可以通过 Pólya 定理更快速地导出结论。讲解可以看 HandWiki、Ency 或 x义x.

(textbf{例 1})：烷基计数