置换群 / Polya 原理 / Burnside 引理 学习笔记
在 GJOI 上做手链强化，经过长达三小时的 OEIS 和手推无果后开摆，喜提 rnk12，故开始学习置换群相关内容。
笔记主要以 Polya 原理和 Burnside 引理的应用为主，所以会非常简单，很大一部分的群论概念和证明不会写，因为我不会。
基础群论
定义
群论主要研究的是一种叫「群」的代数结构。
群，简单来说是一个集合和一种二元运算构成的二元组 \((G, \cdot)\)，并且满足群公理。
群公理：
- 二元运算 \(\cdot\) 要对集合 \(G\) 封闭。
- 满足结合律，即对于元素 \(a, b, c \in G\)，要满足 \((a \cdot b) \cdot c = a \cdot (b \cdot c)\)。
- 有单位元，即存在一个元素 \(e\) 满足对于任意 \(a \in G\) 都有 \(e \cdot a = a \cdot e = a\) 成立。这个元素 \(e\) 被称为「单位元」。
- 任意一个元素都有逆元。即对于任意 \(a \in G\)，一定能找到一个元素 \(a ^ {-1}\) 满足 \(a \cdot a ^ {-1} = e\)，我们称 \(a\) 和 \(a ^ {-1}\) 互为单位元。
子群
对于两个群 \((G, \cdot), (H, \cdot)\)，如果 \(H \subseteq G\) 并且这俩群的 \(\cdot\) 指的是同一个二元运算，那么我们称 \((H, \cdot)\) 是 \((G, \cdot)\) 的一个子群。
阶
群的阶指的是群的集合的元素个数，记作 \(|G|\)。
没了。只是学习利用置换群计数且不管证明的话，只知道这些概念够了。
置换群
置换群是一类被系统研究过的群。
置换的概念
置换是从一个 \(1\) 到 \(n\) 的排列到另一个 \(1\) 到 \(n\) 排列的映射。
例如像这样：
\[\binom{1, 2, 3, 4}{4, 1, 3, 2} \]这个置换会将原排列的 \(1\) 用 \(4\) 代替，\(2\) 用 \(1\) 代替，\(4\) 用 \(2\) 代替。
例如这个置换接收了一个排列 \((3, 1, 2, 4)\)，那么它会将其映射到排列 \((3, 4, 1, 2)\)。
置换群
置换群 \((G, \cdot)\) 中的元素为所有 \(1\) 到 \(n\) 的排列的置换。
两个置换进行 \(\cdot\) 运算可以理解为将这两个置换进行合成。
若 \(a \cdot b = c\)，那么我们对任意一个排列 \(x\) 进行一次 \(a\) 置换变成 \(a(x)\)，然后再对其进行 \(b\) 置换得到 \(b(a(x))\)，得到的结果等于直接对原排列进行 \(c\) 置换 \(c(x)\)。也就是 \(c(x) = b(a(x))\)。
举个例子吧，假设 \(a\) 置换是 \(\large\binom{1, 2, 3, 4}{4, 1, 3, 2}\)， \(b\) 置换是 \(\large\binom{1, 2, 3, 4}{4, 3, 2, 1}\)
那么有：
\[c = a \cdot b = \binom{1, 2, 3, 4}{4, 1, 3, 2} \cdot \binom{1, 2, 3, 4}{4, 3, 2, 1} = \binom{1, 2, 3, 4}{4, 1, 3, 2} \cdot \binom{4, 1, 3, 2}{1, 4, 2, 3} = \binom{1, 2, 3, 4}{1, 4, 2, 3} \]来验证这个群满足群公理。
- 一个置换进行 \(\cdot\) 运算后还是一个置换，显然满足封闭性。
- 试一下就知道结合律是满足的。
- 有单位元，单位元是 \(\large\binom{1, 2, 3, 4}{1, 2, 3, 4}\)。
- 有逆元，交换上下两行即可。
所以这玩意是满足的。
Burnside 引理
设 \(A, B\) 是两个有限集合，\(X\) 是一些 \(A\) 到 \(B\) 的映射的集合。
\(G\) 是 \(A\) 上的置换群，\(X\) 的映射在 \(G\) 的作用下封闭。
\(X / G\) 是 \(G\) 作用在 \(X\) 上的所有等价类的集合。
（如果 \(X\) 中的两个映射经过 \(G\) 的置换后相等，那么这俩映射就在一个等价类中）
那么有：
\[|X / G| = \frac{1}{|G|} \sum_{g \in G} |X ^ g| \]其中 \(|S|\) 是指集合 \(S\) 的元素个数。\(X^g\) 定义如下。
\[X ^ g = \{x | x \in X, g(x) = x\} \]如果有点难懂的话那就举个例子吧。
（因为 OI Wiki 上的正方体的例子需要思考（）所以搬了另一个例子过来）
（出自 集训队论文 符文杰:《Pólya原理及其应用》）
一个简单的例子：
将一个 \(2 \times 2\) 的矩阵黑白染色，问有多少种本质不同的方案？如果两个矩阵可以通过旋转相互吻合，那么算同一种方案。
首先先列出来吧。
不考虑本质不同，一共有 \(16\) 种方案：
其中本质不同的有 \(6\) 种，其他方案都可以由下面的方案旋转得到。
把上面的集合列出来吧。
\(A\)：表示四个格子的集合。
\(B\)：表示黑白两种颜色的集合。
\(X\)：不考虑本质不同，直接在四个格子上染色的方案的集合。每个格子可染可不染，总共有 \(2 ^ 4 = 16\) 种方案。
\(G\)：所有旋转操作构成的置换群。集合中有四个元素，分别是：转 \(0 ^{\circ}\)，转 \(90 ^{\circ}\)，转 \(180 ^{\circ}\)，转 \(270 ^{\circ}\)。（本文内旋转默认顺时针）
\(H / G\)：本质不同的染色方案的集合。
套公式吧，下面来探究 \(G\) 中每个元素 \(X^g\) 是什么。下面分别称四个格子（左上，右上，左下，右下）为 \(1, 2, 3, 4\) 格子。
- 转 \(90 ^{\circ}\)。也就是 \((1, 2, 3, 4)\) 置换为 \((2, 3, 4, 1)\)。要求 \((1, 2), (2, 3), (3, 4),(4, 1)\) 格子颜色一样，也就是所有格子颜色一样，所以一共有 \(2\) 种方案，也就是图中的 C1 和 C2。
- 转 \(180 ^{\circ}\)。也就是 \((1, 2, 3, 4)\) 置换为 \((3, 4, 1, 2)\)。要求 \((1, 3), (2, 4)\) 格子颜色一样。对于每组格子都能选择两种颜色，所以一共有 \(4\) 种方案，也就是图中的 C1，C2，C11，C12。
- 转 \(270^{\circ}\)。也就是 \((1, 2, 3, 4)\) 置换成 \((4, 1, 2, 3)\)。和第一种情况一样，一共有 \(2\) 种方案，C1 和 C2。
- 转 \(0^{\circ}\)。所有方案都满足，所以有 \(16\) 种。
所以根据公式：
\[\begin {aligned} |X / G| &= \frac{1}{|G|} \sum_{g \in G} |X ^ g| \\ &= \frac {2 + 4 + 2 + 16}{4}\\ &= 6 \end {aligned} \]然后我们就得到了本质不同的方案有 \(6\) 种。
这里问题规模较小所以可以枚举解决，但是问题规模增大到 \(20 \times 20\) 甚至 \(200 \times 200\) 的时候靠枚举可就很难解决了。
证明不会。反正 OI 不考证明（）
Polya 原理
数有多少个点置换后不动是不是很烦？那么还有更简单的式子。
定义与 Burnside 引理的定义相同。
如果 \(X\) 是 \(A\) 到 \(B\) 所有的映射，那么有：
\[|X / G| = \frac{1}{|G|} \sum_{g \in G} |B| ^ {c(g)} \]其中 \(c(g)\) 表示对于元素 \(g\)，它能拆成多少个子置换。
举个例子，例如置换
\[g = \binom{1, 2, 3, 4, 5, 6}{1,5, 2, 6, 3, 4} \]我们能把它拆成三个子置换：
\[\binom 11 \ \binom {2, 3, 5}{5, 2, 3} \ \binom {4, 6}{6, 4} \]所以 \(c(g) = 3\)。
这就是 Polya 原理。
上面的例题太简单了，让我们把规模增长到 \(3 \times 3\)。
因为所有的染色方案都是允许的，没有说什么某个格子不能涂黑啊、哪个格子不能涂白啊，所以满足 Polya 原理的前置条件。
讨论每个置换的 \(c(g)\)。为了简便，下面不写置换第一行的 \((1, 2,3, 4, \dots, 9)\)
- 转 \(0 ^{\circ}\)：置换为 \((1, 2, 3, 4, 5, 6, 7, 8, 9)\)，共有 \(9\) 个子置换，\(c(g) = 9\)。
- 转 \(90 ^{\circ}\)：置换为 \((3, 6, 9, 2, 5, 8, 1, 4, 7)\)，共有 \(3\) 个子置换，分别是 \((1, 3, 7, 9)\) 组成的子置换、\((2, 4, 6, 8)\) 组成的子置换和 \((5)\) 组成的子置换。\(c(g) = 3\)。
- 转 \(180 ^{\circ}\)：置换为 \((9, 8, 7, 6, 5, 4, 3, 2, 1)\)，共有 \(5\) 个子置换，除了 \(5\) 以外其他数字都能两两分组组成一个子置换。\(c(g) = 5\)。
- 转 \(270 ^{\circ}\)：置换为 \((7, 4, 1, 8, 5, 2, 9, 6, 3)\)，共有 \(3\) 个子置换，看到自己想必大家都能自己数出来了。\(c(g) = 3\)。
套公式吧。
\[\begin {aligned} |X / G| &= \frac{1}{|G|} \sum_{g \in G} |B| ^ {c(g)} \\ &= \frac{2 ^ 9 + 2 ^ 3 + 2 ^ 5 + 2 ^ 3}{4} \\ &= 140 \end {aligned} \]所以有 \(140\) 种本质不同的染色方案。
感兴趣的读者自己验证吧反正我懒了。
如果你枚举法，那么枚举 \(512\) 种方案非常复杂。即使使用 Burnside 引理，求不动点也就是 \(|X^g|\) 也是很复杂的，这个时候就体现出 Polya 原理的优势了。
例题部分咕着，写完会粘上来的。
标签：格子,Burnside,cdot,置换,circ,Polya,binom,置换群 From： https://www.cnblogs.com/AzusidNya/p/18041954