组合结构符号化学习笔记

x义x · 2020-10-20 14:50:33 · 个人记录

更好的阅读体验

由于在洛谷博客上编辑很不方便，所以最新版本请到上面的链接查看。

最近发现有个叫“解析组合”的东西里面有一些符号化组合对象的工具，学来用一用。pdf 版本在这里。书中举了大量生动的例子，画了大量的插图，非常的强大。如果你的数数不够好，可以找来看一看加深理解。

这里默认读者有一些数数功底，比如至少做过城市规划和无标号树计数。

定义

一个组合类（combinatorial class）是一个可数集合 \mathcal A，以及一个大小函数（size function）f:\mathcal A\rightarrow\mathbb N。记 f(x)=|x|，或者，在某些需要指出组合类的场合下，|x|_{\mathcal A}。

大小函数应该是一个我们很熟悉的东西了。“节点数”“叶子数”……

记对于自然数 n，A_n=\Big|\{x\in \mathcal A,|x|=n\}\Big|。称 A_n 是 \mathcal A 的计数序列（counting sequence）。

一个计数序列的 OGF（ordinary GF）是形式幂级数

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

因而对于组合类 \mathcal A，它的 OGF 也是

\sum_{x\in A}z^{|x|}

我们记

[z^n]A=A_n

熟悉到不能再熟悉了。（不想熟悉）

两个组合类 \mathcal A,\mathcal B 是同构的，如果 A_n=B_n。记作 \mathcal A\cong\mathcal B。

引出的一些组合类

记 \mathcal E 是只由一个大小为 0 的元素构成的组合类。我们有 E(z)=1。

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

几个基础的构造

下面讨论一些可以直接被翻译为生成函数的构造，称为 admissible constructions，可译为“可接受的构造”。具体来说

称一个构造 \Phi admissible，如果

\mathcal A=\Phi[\mathcal B^{(1)},\mathcal B^{(2)},...,B^{(m)}]

中的 \mathcal A 的计数序列 A_n 只依赖于 B_n^{(i)}。也就是说存在一个对应的函数 \Psi，使得

A=\Psi[B^{(1)},B^{(2)},...,B^{(m)}]

笛卡尔积

此时，

也就是普通卷积，从而有

不交并

此时，

和

我们意图扩展不交并的概念。为了绕开多重集，我们使用下面的定义：

\mathcal B+\mathcal C:=(\{\square\}\times \mathcal B)\cup(\{\triangle\}\times\mathcal C)

其中 \square 和 \triangle 是两个不同的，大小为 0 的元素。

我们有

请注意，普通的集合并显然不是 admissible 的。

Sequence 构造

若 [z^0]\mathcal B=0，则我们定义

\text{SEQ}(\mathcal B):=\mathcal E+\mathcal B+\mathcal B\times \mathcal B+\mathcal B\times \mathcal B\times \mathcal B+...

是 \mathcal B 的 Sequence 构造。换句话说，如果 \mathcal A=\text{SEQ}(\mathcal B)，则

\mathcal A=\{(\beta_1,...,\beta_l)\ |\ l\ge 0,\beta\in \mathcal B\}

我们有

Cycle 构造

首先定义本质相同是什么意思。两个元素 \beta_1,\beta_2 在映射群列 G_0,G_1,G_2,... 下本质相同，如果 |\beta_1|=|\beta_2|，且存在映射 g\in G_{|\beta|} 使得 g(\beta_1)=\beta_2。显然此处的本质相同具有自反性、对称性、传递性，从而是一个等价关系。

定义 \mathcal A/G 是一个组合类，其中的元素 \alpha 是一个组合对象的非空集合，\alpha 中的元素互相等价，如果 \alpha_1\neq \alpha_2，则 \alpha_1 和 \alpha_2 中的元素两两不等价。|\alpha|_{\mathcal A/G} 等于任意 \alpha 中元素的大小，显然它们都相等。我们把 \alpha 称为一个等价类（equivalence class）。

若 [z^0]\mathcal B=0，则我们定义

\text{CYC}(\mathcal B):=(\text{SEQ}(\mathcal B)-\mathcal E)/\mathbf S

其中 \mathbf S 是所有循环移位（circular shift）构成的群。

根据 Burnside 引理我们容易得到

Multiset 构造

若 [z^0]\mathcal B=0，则我们定义

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

其中 \mathbf R 是任意置换构成的群。

比如，(\beta_1,\beta_2,\beta_3) 和 (\beta_1,\beta_3,\beta_2),(\beta_2,\beta_1,\beta_3),(\beta_2,\beta_3,\beta_1),(\beta_3,\beta_1,\beta_2),(\beta_3,\beta_2,\beta_1) 等价。这是整个 (\beta_1,\beta_2,\beta_3) 所属的等价类。

再比如，(\beta_1,\beta_1,\beta_2) 和 (\beta_1,\beta_2,\beta_1),(\beta_2,\beta_1,\beta_1) 等价。这是整个 (\beta_1,\beta_1,\beta_2) 所属的等价类。

你可能更熟悉它的另两个名字：Euler 变换或 Polya Exp。

于是有我们熟悉的结论：

Powerset 构造

若 [z^0]\mathcal B=0，则我们定义 \text{PSET}(\mathcal B) 是 \mathcal B 的所有有限子集构成的集合。如果 \alpha\in\text{PSET}(\mathcal B)，则 |\alpha|=\sum_{\beta\in \alpha}|\beta|。

显然有

从而

我们将用以上的几个构造（\mathcal E,\mathcal Z,+,\times,\text{SEQ},\text{CYC},\text{MSET},\text{PSET}）构造出一切组合类。具体来讲

specification，可构造性，Pólya 操作

一个 r 阶的 specification（可译作规范）是 r 条方程构成的方程组

\begin{cases}\mathcal A^{(1)}=\Phi_1(\mathcal A^{(1)},\mathcal A^{(2)},...,\mathcal A^{(r)})\\\mathcal A^{(2)}=\Phi_2(\mathcal A^{(1)},\mathcal A^{(2)},...,\mathcal A^{(r)})\\...\\\mathcal A^{(r)}=\Phi_r(\mathcal A^{(1)},\mathcal A^{(2)},...,\mathcal A^{(r)})\end{cases}

其中 \Phi 都是八大构造构建起的函数。

我们称一组组合类是可构造的，如果它满足一个 specification。

The generating function of a constructible class is a component of a system of functional equations whose terms are built from 八大构造。（前面那段文字翻译不能……）

我们记

它们被称为 Pólya 操作。

那个 Pólya Exp · 改真的不是我乱翻，原文就是 Modified Pólya Exp

Pointing 构造

定义

\Theta\mathcal B:=\sum_{i\ge 0}\{\beta\in \mathcal B,|\beta|=i\}\times\{\epsilon_1,\epsilon_2,...,\epsilon_i\}

其中 \epsilon_i 是大小为 0 的对象。

它没有什么组合意义，因为它可以解释成在一个图 \beta 中指明一个特殊节点（比如根），但是在图计数中使用 OGF 往往是因为无标号，而无标号场合下任何操作都要 /\mathbf R，这使得这个鬼构造什么用也没有。

我们有

Subsitution 构造

定义

\mathcal B\circ\mathcal C:=\sum_{i\ge 0}\{\beta\in\mathcal B,|\beta|=i\}\ {\color{red}\times}\ \mathcal C^{\times i} 这里的 $\color{red}\times$ 较特殊：新的 $|\cdot|$ 定义为 $\sum|\gamma|$。

同上，没有组合意义。

有

Pólya 定理

考虑一个大小为 m 的有限集合 \mathcal M 和一个置换群 G 作用在其上。不妨认为 \mathcal M=\{1,2,...,m\}。

定义 G 的循环指标为

Z(G)=Z(G;x_1,x_2,...,x_m)=\dfrac{1}{|G|}\sum_{g\in G}x_1^{j_1(g)}x_2^{j_2(g)}...x_m^{j_m(g)}

其中 j_1(g) 表示 g 中大小为 1 的循环个数。

一个我们并不陌生的东西。

Pólya 定理. 令 \mathcal B 是一个组合类，\mathcal M 是一个有限集合，上有一个置换群 G。考虑集合 \mathcal B^{\mathcal M}，即所有 \mathcal M\rightarrow\mathcal B 的映射……

我们指出，这是广义的染色。

……两个染色 \phi_1,\phi_2\in\mathcal B^{\mathcal M} 被认为本质相同，如果存在映射 g\in G,\phi_1\circ g=\phi_2。从而我们研究的对象可以称为 \mathcal B^{\mathcal M}/G。

$$ \sum_{\phi\in (\mathcal B^{\mathcal M}/G)}w(\phi)=Z\left(G;\sum_{\beta\in\mathcal B}w(\beta),...,\sum_{\beta\in\mathcal B}w^m(\beta)\right) $$ 如果取 $w(\beta)=z^{|\beta|}$，我们还有 $$ \sum_{\phi\in (\mathcal B^{\mathcal M}/G)}z^{|\phi|}=Z\left(G;B(z),...,B(z^m)\right) $$ 如果取 $G$ 为任意置换的集合 $\mathbf R$，我们还有 $$ \sum_{i=0}^{\infty}\sum_{\phi\in (\mathcal B^{[1..i]}/\mathbf R_i)}w(\phi)=\text{exp}\left(\sum_{i=1}^{\infty}\dfrac{\sum_{\beta\in\mathcal B}w^i(\beta)}{i}\right) $$ 证明可大致参考[这里](https://xyix.gitee.io/posts/?page=1&postid=31)（链接里同时还取 $w(\beta)=z^{|\beta|}$，但是其实不失一般性。注意 $w(\beta)=z^{|\beta|}$ 和 $\text{MSET}$ 的关系。）

《如果早知道，男生也会被真正的 Pólya 定理长这样》

现在运用上面的构造，Burnside 引理和 Pólya 定理，你应该能解决很多无标号计数问题了。可是……标号是什么？我们来介绍有标号计数。

有标号计数

首先定义什么叫做标号。

一个大小为 n 的对象被称作标号的，如果它的每一个节点（这里我们认为一个对象是一个图，如果我们需要的话，可以任意扩展它）都附带一个互不相同的正整数标号，恰好是 [1..n] 的一个排列。

一个对象被称为弱标号的，如果它几乎是标号的，但是其标号不必恰好是 [1..n] 的一个排列。

一个组合类被称作标号的，如果它的元素都是标号的对象。

一个计数序列 A_n 的 EGF（Exponential GF）是形式幂级数

A(z)=\sum_{i\ge 0}A_n\dfrac{z^n}{n!}

因而对于组合类 \mathcal A，它的 EGF 也是

\sum_{x\in \mathcal A}\dfrac{z^{|x|}}{|x|!}

我们记

A_n=n![z^n]A(z)