1.1.3 组合符号化方法(上)

これから僕らは

逃れられない自由の果てに

守られ許されて 生きていくのだ

\[ \rm{Define\ \LaTeX \ Macros\ Here} \newcommand\ag[1]{\left\langle#1\right\rangle} \newcommand\ul[1]{\underline{#1}} \newcommand\stirA[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}} \newcommand\stirB[2]{\begin{Bmatrix}#1\\ #2\end{Bmatrix}} \newcommand\ul[1]{\underline{#1}} \newcommand\dis{\operatorname{dis}} \newcommand\edp{\operatorname{edp}} \newcommand\deg{\operatorname{deg}} \newcommand\pcnt{\operatorname{popcount}} \newcommand\class{\mathcal} \]

主要是无标号体系下的内容。

组合类

定义

我们定义一个组合类 \(\mathcal A\) 是一个可数集合，其中包含了一些组合对象，以及一个附带的大小函数 \(|\cdot|:\mathcal A\rightarrow \mathbb N\)。这个大小函数的例子就是序列长度，树的节点数之类的。

若对于自然数 \(n\)，\(A_n=\operatorname{card}\qty(\{|\alpha |=n,\alpha \in \mathcal A\})\)，则 \(A\) 称为 \(\mathcal A\) 的计数序列。也就是 \(A_n\) 就代表 \(\mathcal A\) 里大小为 \(n\) 的元素有几个。

一个计数序列的 OGF 就是形式幂级数

\[ A(z)=\sum_{i\in \mathbb N}A_iz^i \]

也就是说，对于某个组合类 \(\mathcal A\)，其 OGF 可以写成

\[ A(z)=\sum_{\alpha \in \mathcal A} z^{|\alpha|} \]

这被称为幂表示。

我们定义组合类 \(\mathcal A,\mathcal B\) 的不交并为 \(\mathcal A+\mathcal B\)。

定义两个组合对象 \(\alpha,\beta\) 的有序拼接 \((\alpha, \beta)\) 有 \(|(\alpha,\beta)|=|\alpha|+|\beta|\)。组合类 \(\class A,\class B\) 的笛卡尔积 \(\class A\times \class B\) 是 \(\{(\alpha, \beta)|\alpha \in \class A, \beta\in \class B\}\)。

由定义我们知道

\[ \class C=\class A+\class B\Longleftrightarrow C(x)=A(x)+B(x)\\ \class C=\class A\times \class B\Longleftrightarrow C(x)=A(x)\times B(x) \]

记 \(\class E=\{\epsilon\}\) 是只由一个大小为 \(0\) 的元素构成的组合类，\(E(z)=1\)。且对于任意组合类 \(\class A\)，规定 \(\class A^0=\class E\)。

记 \(\class Z\) 是只由一个大小为 \(1\) 的元素构成的组合类，\(Z(z)=z\)。

组合类的构造

我们试图直接从组合类构造出对应的生成函数，为此，我们需要考察一些组合类的基本构造。

Sequence 构造

我们有一个组合类 \(\class A\)，现在我们要用它生成一个不定长序列，每一个位置都是 \(\class A\) 中的一个元素，不妨把这个操作生成的不定长序列的组合类称为 \(\textsf{SEQ}(\class A)\)，则

\[ \textsf{SEQ}(\class A)=\class E+\class A+\class A\times \class A+\cdots =\sum_{k=0}^{\infty}\class A^k \]

对于记 \(\class B=\textsf{SEQ}(\class A)\)，这就是说

\[ B(x)=\sum_{k=0}^{\infty}A^k(x)=\frac{1}{1-A(x)} \]

Amplification 构造

组合类 \(\class A\) 的 Amplification 构造 \(\textsf{AMP}(\class A)\) 是由所有 \(\class A\) 中的元素 \(\alpha\)，将自己复制在自己后面任意多次组成的。

也就是说：

\[ \textsf{AMP}(\class A)=\bigcup_{\alpha \in \class A}\qty(\textsf{SEQ}(\{\alpha\})) \]

一个元素 \(\alpha\) 将自己复制 \(k\) 遍，那么新的元素大小应为 \(k|\alpha|\)，所以此变换有：

\[ \class B=\textsf{AMP}(\class{A})\Longleftrightarrow B=\sum_{i\ge 0}A(z^i) \]

更常用的是其带限制的形式，即 \(\textsf{AMP}_k\) 构造。

\[ \textsf{AMP}_k(\class A)=\{\overbrace{\alpha\alpha\alpha\alpha\cdots\alpha}^{\text{恰好 }k\text{ 个}}:\alpha \in \class A\} \]

所以

\[ \class B=\textsf{AMP}_k(\class{A})\Longleftrightarrow B=A(z^k) \]