抄袭 x义x 的 Symbolic Method 讲义
Aleph1022
·
·
个人记录
引言
“生成函数”是组合对象在度量上的投影。 ——EntropyIncreaser
（生成函数）蕴含的初等运算恐怕并不足够具有洞察力以支持得到，通过特殊的组合对象得出的结论的水平。 ——EntropyIncreaser
解析组合试图从一个较为机械化的方式帮助我们将组合计数问题从模型直接转为生成函数。——EntropyIncreaser
组合结构符号化，（大概）也就是上面提到的解析组合，一般也叫 Symbolic Method 即符号化方法。这是一种相对优越的审视生成函数与组合对象的关联的角度。
活用这种方法，就可以跳过 DP 直接写出生成函数，并对生成函数和组合意义的联系有更深刻的理解。
组合类 & OGF & 无标号计数
定义（组合类）：一个组合类，或简称类，是一个有限或可数的集合，其上定义了大小函数，满足：
- 一个元素的大小是一个非负整数。
- 对任意非负整数 k，大小为 k 的元素个数是有限的。
如果 \mathcal A 是一个类，其中元素 \alpha \in \mathcal A 的大小记作 |\alpha| 或 |\alpha|_{\mathcal A}。
再定义 \mathcal A_n = \{\alpha \mid \alpha \in \mathcal A \land |\alpha|_{\mathcal A} = n\}，记 A_n = |\mathcal A_n|（或 a_n）。
定义（计数序列）：称 \{A_n\} 是 \mathcal A 的计数序列。
定义（OGF）：一个序列 \{A_n\} 的普通生成函数（OGF）是形式幂级数
A(z) = \sum\limits_{n\ge 0} A_n z^n
一个组合类 \mathcal A 的 OGF 就是其计数序列的 OGF。等价地，其也是
A(z) = \sum\limits_{\alpha \in \mathcal A} z^{|\alpha|}
约定两个基础的组合类 \mathcal E,\mathcal Z 分别是只有一个大小为 0 和 1 的元素的组合类，对应 GF E(z) = 1,Z(z)=z。
形式幂级数
形式幂级数可以看作是多项式的拓展，但是其可以有无限项，且不需要考虑敛散性。
换句话说，这里的 z 并不是一个实际的数，它只是一个被定义满足普通的幂的运算法则的记号。
可以证明，形式幂级数的四则运算都是正确的。
Example 1
考虑 \texttt0,\texttt1 组成的串的组合类 \mathcal W，其中字符集可以视作组合类 \mathcal A = \{\texttt0,\texttt1\}。那么
\mathcal W = \{\epsilon,\texttt0,\texttt1,\texttt{00},\texttt{01},\texttt{10},\texttt{11},\dots\}
其中 \epsilon 表示空元素。
显然其计数序列就是 W_n = [z^n] W(z) = 2^n。
构造组合类
组合类是由其他更本质，更微观的组合类构造而成。这里的构造是组合类到组合类的映射。
如果一个构造可以和 GF 的形式对应，我们就称其可以翻译为 GF。
接下来我们来讨论一些经典构造，它们都可以翻译为 GF。
笛卡尔积
给定组合类 \mathcal B,\mathcal C，其笛卡尔积记作组合类 \mathcal A = \mathcal B \times \mathcal C，其中
\mathcal A = \{(\beta,\gamma)\mid \beta \in \mathcal B,\gamma \in \mathcal C\}
大小函数定义为
|(\beta,\gamma)|_{\mathcal A} = |\beta|_{\mathcal B} + |\gamma|_{\mathcal C}
翻译到 GF，其实就是卷积罢了。
即
A(z) = B(z)C(z)
不交并
给定组合类 \mathcal B,\mathcal C，其中 \mathcal B \cap \mathcal C = \varnothing，则其不交并记作 \mathcal A = \mathcal B \cup \mathcal C，其大小函数定义为
|\alpha|_{\mathcal A} = \begin{cases}
|\alpha|_{\mathcal B}, & \alpha \in \mathcal B \\
|\alpha|_{\mathcal C}, & \alpha \in \mathcal C
\end{cases}
则就是 GF 的加法
A(z) = B(z) + C(z)
不过有了笛卡尔积之后，我们可以将并描述得更好：
\mathcal A = \mathcal B + \mathcal C = (\mathcal E_1 \times \mathcal B) \cup (\mathcal E_2 \times \mathcal C)
其中相当于用不占大小的两种元素区分了两个组合类中的元素。
Example 2
回顾 Example 1，我们注意到其实 \mathcal W 中的每个非空元素都是 \mathcal W 中的某个元素多添加一个字符构成的，也就是
\mathcal W = \mathcal E + \mathcal W \times \mathcal A
我们可以知道
W(z) = 1 + 2z \cdot W(z)
也就是
W(z) = \frac1{1-2z}
这和我们显然得到的结果 W_n = 2^n 一致。
序列
给定组合类 \mathcal A，我们定义其 Sequence 构造描述了以 \mathcal A 中的元素组成的所有不定长序列，记作
\mathrm{SEQ}(\mathcal A) = \mathcal E + \mathcal A + \mathcal A \times \mathcal A + \mathcal A \times \mathcal A \times \mathcal A + \cdots
不过我们要求 A_0=0，否则这个组合类并不是良定义的。
翻译成 GF，就是
\sum\limits_{k\ge 0} A^k(z) = \frac1{1-A(z)}
环
给定组合类 \mathcal A，我们定义其 Cycle 构造描述了以 \mathcal A 中的元素组成的所有环，记作
\mathrm{CYC}(\mathcal A) = (\mathrm{SEQ}(\mathcal A) \mathop{\backslash} \mathcal E) / \mathbf S
其中 \mathbf S 是所有循环移位构成的群。
由于今天不是讲群论，所以这里直接给出结论：通过 Burnside 引理可知其对应的 GF 为
\sum\limits_{k\ge 1} \frac{\varphi(k)}k \ln \frac1{1-A(z^k)}
多重集
给定组合类 \mathcal A，我们定义其 Multiset 构造描述了以 \mathcal A 中的元素组成的所有多重集，记作
\mathrm{MSET}(\mathcal A) = \mathrm{SEQ}(\mathcal A) / \mathbf R
其中 \mathbf R 是所有置换构成的群。
在无标号计数中非常重要。其（翻译到 GF 上的操作）也称作 Polya Exp，欧拉变换等。
将其翻译到 GF，可以使用 Polya 定理，但是没有必要，所以我们直接给出一个方法：考虑多重集可以转化为钦定某种顺序的序列，那么我们注意到考虑每种元素的贡献，这其实是
\prod\limits_{\alpha \in \mathcal A} \mathrm{SEQ}(\{\alpha\})
GF 就是
\prod\limits_{i\ge 1} \frac1{(1-z^i)^{A_i}} = \exp\left(\sum\limits_{i\ge 1} \frac{A(z^i)}i\right)
这个等号不展开证明，可以自行对左侧式取 \ln 手动分析。
将其记作 \,\mathrm{Exp}(A(z))。
EGF & 有标号计数
定义组合类的 EGF 是
A(z) = \sum\limits_{\alpha \in \mathcal A} \frac{z^{|\alpha|}}{|\alpha|!}
可以验证其笛卡尔积和不交并的 GF 翻译是不变的。
序列
可以发现这也和 OGF 一致。就是
\frac1{1-A(z)}
集合
给定组合类 \mathcal A，我们定义其 k-Set 构造描述了以 \mathcal A 中的元素组成的所有 k 元集，记作
\mathrm{SET}_k(\mathcal A)
定义其 Set 构造描述了所有集合，记作
\mathrm{SET}(\mathcal A) = \sum\limits_{k\ge 0} \mathrm{SET}_k(\mathcal A)
即
\frac1{k!} A^k(z)
和
\sum\limits_{k\ge 0} \frac1{k!} A^k(z) = \exp A(z)
环
给定组合类 \mathcal A，我们定义其 k-Cycle 构造描述了以 \mathcal A 中的元素组成的所有 k 元环，记作
\mathrm{CYC}_k(\mathcal A)
定义其 Cycle 构造描述了所有环，记作
\mathrm{CYC}(\mathcal A) = \sum\limits_{k\ge 0} \mathrm{CYC}_k(\mathcal A)
即
\frac1k A^k(z)
和
\sum\limits_{k\ge 0} \frac1k A^k(z) = \ln \frac1{1-A(z)}