2.【理论】群与对称

\[ \rm{Define\ \LaTeX \ Macros\ Here} \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\Endpos{\operatorname{Endpos}} \newcommand\Startpos{\operatorname{Startpos}} \newcommand\height{\operatorname{height}} \newcommand\SA{\operatorname{SA}} \newcommand\len{\operatorname{len}} \newcommand\chkmax{\operatorname{chkmax}} \newcommand\chkmin{\operatorname{chkmin}} \newcommand\siz{\operatorname{siz}} \newcommand\fa{\operatorname{fa}} \newcommand\LCP{\operatorname{LCP}} \newcommand\EGF{\operatorname{EGF}} \newcommand\OGF{\operatorname{OGF}} \newcommand\bd{\operatorname{Border}} \newcommand\mbd{\operatorname{MaxBorder}} \]

本节内容是下一节部分内容的基础，但不会本节的内容也不影响你阅读下一节的大部分内容。

群的引入¶

假设我们有一个对称的操作的集合 \(G\)，组合对象的全集记为 \(X\)，一个组合对象 \(x\) 能够通过 \(G\) 中的操作生成其他的组合对象。我们说这些组合对象等价，需要计数所有等价类的个数。

例子

给一个 \(n\) 元环节点标号，两个环同构（事实上环上就是能通过旋转重合），则视为同一个环。
给一个立方体的 \(6\) 个面涂上颜色，如果两个立方体能够通过旋转重合，则视为同一个立方体。
……

为了给这些计数问题一个通用的解决方法，我们就必须研究这些对称操作组成的结构。

若 \(x,y\) 两个对象本质属性相同，则我们说 \(x\sim y\)。我们说 \(f\) 是一个对称操作，其作用在 \(x\) 上的结果记作 \(f(x)\)，那么有 \(\forall x\in X,x\sim f(x)\)，也就是任意一个对象 \(x\) 在 \(f\) 的作用下本质属性都不改变。

若 \(f,g\) 都是对称操作，那么 \(x\sim g(x)\)，自然有 \(g(x)\sim f(g(x))\)。也就是说先执行 \(f\)，再执行 \(g\)，这两步合在一起的变换也是一个对称操作。我们把这个操作记作 \(f\circ g\)，那么就是说 \(\forall f,g\in G,f\circ g\in G\)。
对于离散的对象来说，对称总是一种保持结构不变的重标号方式。也就是说 \(f\) 是一个函数 \([n]\rightarrow [n]\)，函数复合必然有结合律，即 \(\forall f,g,h\in G,(f\circ g)\circ h=f\circ (g\circ h)\)。
必然存在 \(e\in G\)，\(e(x)=x\)，因为什么都不做同样不会改变其本质属性。
由于 \(x\sim f(x)\)，那么就必然有 \(f(x)\sim x\)，如果将 \(x\) 看作是 \(f(x)\) 施加操作才得到的，那么就必然 \(\exists f^{-1} \in G\)，\(f(x)\sim (f^{-1}\circ f)(x)\)，也就是说 \(\forall f\in G,\exists f^{-1}\in G,f^{-1}\circ f=e\)。

通过上面的讨论，我们可以说：对称操作集合 \(G\) 在操作复合运算 \(\circ\) 下构成一个群。对称变换是群 \(G\) 对组合对象集合 \(X\) 的群作用。我们要计数的东西就是等价类集合 \(X/G\) 的大小 \(|X/G|\)。

轨道-稳定子群定理¶

有几个结构是值得我们注意的

对象 \(x\) 的轨道 \(O_x=\{f(x):f\in G\}\)，也就是 \(x\) 的等价类集合。
稳定子群 \(G_x=\{f\in G:f(x)=x\}\)，也就是作用在 \(x\) 不变的那些变换组成的集合。它是 \(G\) 的子群是易证的。
不动点 \(X^g=\{x\in X:g(x)=x\}\)，在 \(g\) 作用下不变的结构。

对于前两个结构，我们有轨道-稳定子群定理

\[ \forall x\in X,|O_x|\cdot |G_x|=|G| \]

这个形式一看就像拉格朗日定理啊！事实上一种证明方法就是在轨道与 \(G_x\) 在 \(G\) 中的左陪集建立双射，不过我们这里不这么干。我们用更简单的另一种理解方式。

我们知道

\[ |G|=\sum_{y\in O_x}|G_{x\rightarrow y}| \]

引理

若 \(f(x)=y\)，则 \(\{f\circ g: g\in G_x\}=G_{x\rightarrow y}\)，\(|G_x|=|G_{x\rightarrow y}|\)。

人话就是，无论是哪个 \(f\in G_{x\rightarrow y}\)，通过右复合上所有 \(g\in G_x\)，都能生成整个 \(G_{x\rightarrow y}\)。

让我们来证明这个引理

首先，我们证明 \(\{f\circ g:g\in G_x\}\subseteq G_{x\rightarrow y}\)。

这是显然的，因为 \(f(g(x))=f(x)=y\)。
下一步，我们证明 \(\{f\circ g:g\in G_x\}=|G_x|\)。

这也是显然的，即证明 \(\forall g_1,g_2\in G_x,g_1\neq g_2\Longrightarrow f\circ g_1\neq f\circ g_2\)。反证，假设成立，右消去律告诉我们 \(g_1=g_2\)，矛盾。

结合 1，这告诉我们 \(|G_x|\le |G_{x\rightarrow y}|\)。
接下来，我们证明 \(|G_{x\rightarrow y}|\le |G_x|\)，故技重施即可。我们随意选择一个 \(g\in G_{y\rightarrow x}\)，那么 \(\forall h\in G_{x\rightarrow y},h\circ g(x)=x\)（注意这里 \(f\circ g\) 并非单位元）。那么对于同一个 \(g\)，左消去律告诉我们所有的 \(h\circ g\) 必定两两不同，所以 \(|\{h\circ g:h\in G_{x\rightarrow y}\}|=|G_{x\rightarrow y}|\)，又有 \(\{h\circ g:h\in G_{x\rightarrow y}\}\subseteq G_x\)，故 \(|G_{x\rightarrow y}|\le |G_x|\)。Q.E.D！

有了 \(|G_{x\rightarrow y}|=|G_x|\) 这个引理，一切就变得容易了。

\[ |G|=\sum_{y\in O_x}|G_{x\rightarrow y}|=|O_x|\cdot |G_x| \]

Burnside's Lemma¶

又叫 Not Burnside's Lemma。

我们再考察上面的第三个结构：不动点。

\[ \sum_{x\in X,g\in G}[g(x)=x]=\sum_{g\in G}X^g=\sum_{x\in X}G_x \]

然后想想我们怎么表示轨道数 \(|X/G|\)。对每个轨道，我们要让所有 \(y\in O_x\) 加起来恰好是 \(1\)，立即有：

\[ |X/G|=\sum_{x\in X}\frac{1}{|O_x|}=\sum_{x\in X}\frac{|G_x|}{|G|}=\frac{1}{|G|}\sum_{g\in G}|X^g| \]

这就是 Burnside's Lemma：轨道数=所有变换不动点个数的平均值。

我们还可以证明其带权的版本：若权值函数 \(w(x)\) 满足 \(x\sim y\Longrightarrow w(x)=w(y)\)，我们就可以定义 \(w(O_x)=w(x),x\in X\)。

\[ \sum_{O\in G}w(O)\sum_{x\in X}\frac{w(x)}{|O_x|}=\sum_{x\in X}\frac{w(x)|G_x|}{|G|}=\frac{1}{|G|}\sum_{g\in G}\sum_{x\in X^g}w(x) \]

Pólya enumeration theorem(PET)¶

虽然我们常见的 Pólya 是不带权的那个版本，但笔者认为其带权版本更能凸显出其相较于 Burnside 在视角上的不同以及在分析结构上的作用。此外，本章的目的是为下一节的组合符号化服务，而在下一节中我们必须用到带权的版本。因此，我们会先证明带权版本，再得到不带权的版本。

Pólya enumeration theorem

设群 \(G\) 是一个置换群，\(X\) 是一个大小为 \(n\) 的（对象）集合，\(Y\) 是一个大小为 \(m\) 的（颜色）集合

设 \(Y^X\) 表示所有 \(X\rightarrow Y\) 的映射组成的集合，一个这样的映射我们称之为染色。

对于每个 \(y\in Y\)，都有其权值 \(w(y)\)，定义一个映射的权值 \(\displaystyle w(\phi)=\prod_{k=1}^{n}w(\phi(k))\)

若 \(\exists g\in G\) 使得映射 \(\phi_2\) 是置换 \(g\) 作用在映射 \(\phi_1\) 定义域 \(X\) 上的结果，那么我们认为 \(\phi_1\) 与 \(\phi_2\) 等价，显然 \(w(\phi_1)=w(\phi_2)\)，因为置换只会重新排列 \(X\) 中的 \(n\) 个对象，不会改变每种颜色的个数。

那么我们有所有等价类的权值之和为

\[ \sum_{\phi \in (Y^X/G)}w(\phi)=\frac{1}{|G|}\sum_{g\in G}\prod_{i=1}^{m}x_i^{c_i(g)} \]

其中 \(c_i(g)\) 是置换（排列）\(g\) 的大小为 \(i\) 的置换环个数。

需要注意的是两者群作用对象的不同。在 Burnside's Lemma 中，群 \(G\) 是作用在染色方案上的。也就是说，所有染色方案中，在群 \(G\) 中的作用下有哪些是等价的。这里主要的考察对象是已经染色的结构。而 PET 中群 \(G\) 是作用在 \(n\) 个对象上的，其更关心的是 \(n\) 个对象在群 \(G\) 的作用下形成的轮换结构，先考虑结构的对称性，再加上染色的影响。