「学习总结」群 置换群
群，一种特殊的代数结构，满足封闭性、结合律、存在幺元和对于每个元素存在逆元的四种性质。
置换群，一种特殊的群，其中的元素描述了一种交换操作。 # 群论简介 ## 定义 称 集合 \(S\) 和 \(S\) 上运算 \(\cdot\)，共同构成得代数结构记作 \((S, \cdot)\)，为一个群，当且仅当其满足如下性质：
- \(S \not = \varnothing\)
- 封闭性：\(\forall a, b\in S, a\cdot b \in S\)
- 结合律：\(\forall a, b, c\in S, a \cdot (b \cdot c)= (a \cdot b) \cdot c\)
- 幺元：\(\exists e \in S, \forall a \in S, e \cdot a = a \cdot e= a\)
- 逆元：\(\forall a \in S, \exists b \in S, a \cdot b = e\)
几个栗子
- 实数集与实数间的乘法 \((\mathbb{R}, \times)\) 不是群，元素 \(0 \in \mathbb{R}\)，但是 \(0\) 不存在逆元。
- \((\mathbb{R'}, \times)\) 是一个群，幺元为 \(1\)。 其中 \(\mathbb{R'} = \\{\ x\ |\ x\in \mathbb{R}\ \land \ x \not = 0\ \\}\)
- \((\mathbb{Z}, +)\) 是一个群，幺元是 \(0\)。
- \((\mathbb{R}, +)\) 是一个群，幺元是 \(0\)。
- \((\mathbb{P}, \times)\) 是一个群，幺元是 \(1\) ，其中 \(P\) 为某个质数的剩余系。
一类特殊的群
- 阿贝尔群：除了满足群的性质，还需要满足 \(a \cdot b = b \cdot a\) 即 交换律。
置换群
不严谨定义
把 \(1\) ~ \(n\) 个对象 进行交换操作的群，置换群中集合的元素描述了一种交换操作。 对应的，置换群的运算就是分别执行两种交换操作。
一种描述交换操作（置换）的记号。
举个栗子： 给执行交换操作前的元素依次编号为 \(1, 2, 3, 4\)（对编号后，编号为 \(i\) 元素简称元素 i） ，交换操作后变为 \(3, 1, 2, 4\)。
可以描述成 \((1, 2, 3)(4)\)，读作：将元素 \(1\) 换到位置 \(2\)，将元素 \(2\)，换到位置 \(3\)，将元素 \(3\) 换至位置 \(1\)，将元素 \(4\) 换至位置 \(4\)。
可以考虑成： 一张包含 \(n\) 个点的图，然后使 点\(i\) 与 点\(a_i\) 有边相连。对于每个连通块来说，图的形态一定是一个环，从环上一个点开始按照任意方向遍历图，得到的遍历顺序就是上面描述中的一个括号内的内容。联通块的个数就是上面描述中的括号数量，其实这个可以被称为轨道数。
交换群的栗子： 一个对 \(3\) 个元素的交换群：\(\\{e,(1,2)(3),(1,3)(2),(1,2,3),(1,3,2),(2,3)(1)\\}\)
\((1)(2) \cdots (n)\) 简记为 \(e\) 即 对原元素不做交换。
burnside 引理
QAQ
简化定义
设要对 \(n\) 个元素用 \(m\) 种颜色染色，对应置换群为 \(S\)，在该置换群下任意一种得到的相同方案算同一种方案。求本质不同的染色方案数。
根据 burnside 引理，其答案为。 \[ \begin{equation} ANS = \frac{1}{|S|}\sum_{s \in S}\limits{m^{\eta(s)}} \label{bns} \end{equation} \] 其中 \(\eta(s)\) 为置换方案 \(s\) 的轨道数。 这是关于 burnside 引理的一个简化版定义。
一个栗题： \(n\) 个排成一圈的点用 \(m\) 种颜色染色，问方案数（旋转前后的方案为一种方案）.
solution
显然需要解决两个问题： - 置换群的构造. - 置换群元素轨道数目.
考虑这个置换群的置换集合可以是什么： (假设 \(n\) 为 \(6\)). \[ \begin{equation*} S = \begin{Bmatrix} (1)(2)(3)(4)(5)(6), \\\\ (1, 2, 3, 4, 5, 6), \\\\ (1, 3, 5) (2, 4, 6) \\\\ (1, 4) (2, 5) (3, 6) \\\\ (1, 5, 3) (2, 6, 4) \\\\ (1, 6, 5, 4, 3, 2) \\\\ \end{Bmatrix} \end{equation*} \] 分别对应转动的位置个数为 \(0\) ~ \(n - 1\)。稍微模拟一下这个过程，显然移动 \(k\) 个位置的方案，轨道数为 \(\operatorname{gcd}(k, n)\). 然后就一般化了.
完整定义
设 \(A\) 和 \(B\) 为有限集合，\(X = B^A\) 表示从 \(A\) 到 \(B\) 的映射。\(G\) 是 \(A\) 上置换群，\(X / G\) 表示 \(G\) 作用在 \(X\) 上产生的所有等价类集合，若存在两种映射经过 \(G\) 的置换作用后是相同的，则将两种映射视为同一种。 burnside 引理指出： \[ \begin{equation} |X / G| = \frac{1}{|G|}\sum_{g \in G} \limits{|X^g|} \label{burnside} \end{equation} \] 其中 \(X^g\) 表示在映射集合 \(X\) 中有多少元素可以经过 \(g\) 的变化，变成一样的。
考虑与之前定义 \((\ref{bns})\) 的联系： - 一种染色方案可以看成 元素 和 颜色 的映射。 - 对于置换 \(s\) ，如果要保证其作用前后映射方案相同，必须要保证其同轨道内的元素被映射到了同一元素，即 染成了相同的颜色。 - 那么考虑置换 \(s\) 的每一条轨道 \(\eta\)，每一条轨道颜色相同的方案数就是 \(m^{\eta(s)}\) - 这与 \((\ref{burnside})\) 的定义是相符的。
一道例题 众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
现在有一个迷宫，这个迷宫是由若干个正 \(n(=4,6)\) 边形组成的k层迷宫。如果 \(k=1\) ，那么该迷宫就由单独一个正 \(n\) 边形组成；如果 \(k>1\)，则在 \(k−1\) 层的基础上，沿着所有最外层的边增加一个正 \(n\) 边形，新增加的正 \(n\) 边形若有重叠，则保留其中一个即可。具体可以参考下图：
现在为了打破迷宫的结界，你需要在迷宫的某些边上开一扇门。你总共需要开 \(r\) 扇门，每条边最多打开一扇门。但是如果两种开门的方案通过旋转相同，那么视为同一种方案。以及由于是死亡迷宫，所以死了也是可以的，所以你并不需要保证你开门的方案能够让你走出去。求总共的方案数。
solution
现在可以简化一下描述一种操作的语言，burnside 引理 不关心置换的具体对象，只关心置换的大小和出现次数。可以用简写 \((a)^b\) 表示：有 \(b\) 个长度为 \(a\) 的轨道。 先特殊考虑一下 \(k = 2\) 的情况，一共有 \(16\) 条边。可以分为转 \(0^o,90^o,180^o, 270^o\). - 转 \(0^o\) 的置换，可以描述为 \((1)^{16}\). - 转 \(90^o\) 的置换，可以描述为 \((4)^4\). - 转 \(180^o\) 的置换，可以描述为 \((2)^8\). - 转 \(270^o\) 的置换，可以描述为 \((4)^4\).
特殊化一下，不难发现就是：（一共有 \(4k^2\) 条边）
- 转 \(0^o\) 的置换，可以描述为 \((1)^{4k^2}\).
- 转 \(90^o\) 的置换，可以描述为 \((4)^{k^2}\).
- 转 \(180^o\) 的置换，可以描述为 \((2)^{2k^2}\).
- 转 \(270^o\) 的置换，可以描述为 \((4)^{k^2}\).
根据 \(X^g\) 的定义——表示在映射集合 \(X\) 中有多少元素可以经过 \(g\) 的变化，变成一样的。我们始终要保证对于一种置换，同一轨道的元素完全相同. 所以对于第一种置换，贡献就是在轨道数中选出 \(r\) 个让他们都变成 “有门存在” 的状态，即 \(\dbinom{4k^2}{r}\). 其余的同理，答案就是。 \[ \begin{equation} \frac{1}{4}\sum_{g\in G}\limits{\dbinom{\eta(g)}{\frac{r}{t}}} \end{equation} \] 其中 \(t\) 为 轨道 \(g\) 的循环长度。 当 \(\frac{r}{t}\) 不是整数的时候，贡献为 \(0\) ，因为 不存在某种染色方法，使得这种置换中同轨道的元素颜色相同.
适用于立体图形的 burnside 引理
包括对正 \(n\) 面体和足球的 面，点或棱染色。 #### 立方体面染色 首先讨论置换群： 考虑正方体有 \(12\) 条棱，\(6\) 个面，\(8\) 个点。
| 旋转轴类型 | 角度 | 数量 | 置换 |
|---|---|---|---|
| 不转 | \(0^o\) | 1 | \((1)^6\) |
| 面面 | \(90^o\) | 3 | \((1)^2(4)^1\) |
| 面面 | \(180^o\) | 3 | \((1)^2(2)^2\) |
| 面面 | \(270^o\) | 3 | \((1)^2 (4)^1\) |
| 棱棱 | \(180^o\) | 6 | \((2)^3\) |
| 点点 | \(120^o\) | 4 | \((3)^2\) |
| 点点 | \(240^o\) | 4 | \((3)^2\) |
关于角度的确定：观察旋转轴图形周围的形状。数量为总数的一半。
正十二面体染色
\(20\) 个点，\(12\) 个面，\(30\) 条棱，面为五边形。
循环节：即对于一种置换方案的轨道长度。简单理解为转多少次能够转到原来的位置。
以某个对象为旋转轴，其置换群中必然有两个长度为 \(1\) 的轨道，作为旋转轴的对象，旋转前后应该是重叠的。 然后剩下的根据轨道循环节直接算出即可。 可以发现这是一个无脑的工作
足球的置换群
qaq
实在不想写了…… 足球的点数不好求，但是可以根据立体图形外角和公式求出： 立体图形外角和为 \(720^o\) 。 即 \(\text{点数} \times \text{外角度} = 720^o\).
例题：
待填。
题外话
呵呵
