「符号化方法」笔记

· · 算法·理论

定义

符号化方法（symbolic method）是将组合对象快速转换成生成函数的一种方法。

称一个组合类为 (\mathcal A,|\cdot|)，其中 \mathcal A 为组合对象的集合，|\cdot| 是将每一个组合对象映射为一个非负整数（不能是正无穷）的映射关系，称为大小函数。

无标号体系

在无标号体系中将使用普通生成函数（ordinary generating function, OGF）。集合 \mathcal A 对应的生成函数为

A(x)=\sum_{\alpha\in\mathcal{A}}x^{|\alpha|}

记 \mathcal A_n=\{\alpha\in\mathcal A\left|\ |\alpha|=n\right.\},a_n=|\mathcal A_n|，则

A(x)=\sum_{i=0}^{+\infty}a_ix^i

两种特殊的组合类和组合对象：

  • 中性对象（neutral object）\epsilon，满足 |\epsilon|=0；中性类（neutral class） \mathcal E=\{\epsilon\}。中性类的 OGF 为 E(x)=1。
  • 原子对象（atom object）\circ，满足 |\circ|=1；原子类（atom class）\mathcal Z=\{\circ\}。原子类的 OFG 为 Z(x)=x。

（原子对象有时也用 \bullet 表示。）

对于两个组合类 \mathcal A,\mathcal B 在组合意义上同构记为 \mathcal A=\mathcal B，当该同构不平凡时记为 \mathcal A\cong\mathcal B。

有

\mathcal A\cong\mathcal E\times\mathcal A\cong\mathcal A\times\mathcal E

其中 \times 为笛卡尔积。

集合的（不相交）并构造

对于类 \mathcal A,\mathcal B 的并记为

\mathcal A+\mathcal B=(\mathcal E_1\times\mathcal A)+(\mathcal E_2\times B)\\ \mathcal E_1\neq\mathcal E_2

即对类 \mathcal A,\mathcal B 分别染色，如此定义可以避免集合相交的情况出现。

对应的 OGF 为

A(x)+B(x)\\ =\sum_{i=0}^{+\infty}(a_n+b_n)x^i

集合的笛卡尔积构造

定义序偶 ⟨a,b⟩ 的大小为 |a|+|b|。则对于类 \mathcal A\times\mathcal B，其对应的 OGF 为

A(x)\cdot B(x)\\ =\sum_{i=0}^{+\infty}\sum_{j=0}^{+\infty}a_ib_ix^{i+j}\\ =\sum_{n=0}^{+\infty}\sum_{i=0}^{n}a_ib_{n-i}x^n\\

集合的 Sequence 构造

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

定义

\text{SEQ}(\mathcal A)=\mathcal E+\sum_{i\geq1}\mathcal A^i

且要求 \mathcal A_0=\varnothing，也就是 \mathcal A 中没有大小为 0 的对象。

对应 OGF 为

Q(A(x))=1+A(x)+A(x)^2 +\cdots=\frac{1}{1-A(x)}

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

集合的 Multiset 构造

Multiset 构造生成了所有可能的无序组合。

定义

\text{MSET}({\alpha_0,\alpha_1,\cdots,\alpha_n})=\text{MSET}({\alpha_0,\alpha_1,\cdots,\alpha_{n-1}})\times\text{SEQ}(\{\alpha_n\})

即

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

且 \mathcal A_0\neq\varnothing。

或

\text{MSET}(\mathcal A)=\text{SEQ}(\mathcal A)/\mathbf R

其中 \mathbf R 表示等价关系：组成相同但顺序不同。

对应 OGF 为

\text{Exp}(A(x))=\prod_{\alpha\in\mathcal A}(1-x^{|\alpha|})^{-1}=\prod_{i=1}^{+\infty}(1-x^i)^{-a_i}

其中 \text{Exp} 为 Pólya 指数（Euler 变换）。

由麦克劳林公式，得

\ln(x+1)=\frac{x}{1}-\frac{x^2}{2!}+\frac{2!x^3}{3!}-\cdots\\ =\frac{x}{1}-\frac{x^2}{2}+\frac{x^3}{3}-\cdots\\ =\sum_{i=1}^{+\infty}\frac{(-1)^{i-1}x^i}{i}

则

\text{Exp}(A(x))=\prod_{i=1}^{+\infty}(1-x^i)^{-a_i}\\ =\exp\left(\sum_{i=1}^{+\infty}-a_i\cdot\ln(1-x^i)\right)\\ =\exp\left(\sum_{i=1}^{+\infty}a_i\sum_{j=1}^{+\infty}\frac{x^{ij}}{j}\right)\\ =\exp\left(\sum_{i=1}^{+\infty}\frac{\sum_{j=1}^{+\infty}a_jx^{ij}}{i}\right)\\ =\exp\left(\sum_{i=1}^{+\infty}\frac{A(x^i)}{i}\right)\\

（未完）