OI群论入门
Scarlet_Hypoc
·
2020-06-16 13:04:13
·
个人记录
建议到博客内看，不然可能有LaTeX爆炸问题？
废话
群论好强啊……
但其实并不是个太难理解的东西呢qwq。
为了方便理解，不会有出现大量数学符号堆在一起的地方。
下面进入正题 。
群
定义
群其实就是一个集合加上了若干个限制。
一般将群记作 (G,*) ，G 是一个集合，* 是集合 G 内的二元 运算。（* 可以是 +~-~\times~\div 甚至是 \cup~\cap ，这取决于集合 G 内的元素是什么，以及你想怎么用这个群）
对于一个群 (G,*) ，需要满足：
封闭性： 对于任意 a,b\in G ，一定满足 (a*b)\in G 结合律： 对于任意 a,b,c\in G ，一定满足 a*(b*c)=(a*b)*c 有单位元： 集合 G 中一定包含一个元素 e ，满足对于任意 a\in G ，都有 a*e=a ，我们将这个 e 记为单位元，一个群内的单位元是唯一的存在逆元： 对于任意 a\in G ，都存在 b\in G 满足 a*b=e
打个比方，(Z,+) 就是一个群，对于任意整数 a,b ，a+b 也一定是整数，故 a+b 也在 Z 中（封闭性 ），加法显然满足结合律 ，0 就是单位元，对于任意整数 a ，它的逆元就是 -a ，也在 Z 中。
相关概念
阶： G 集合的大小称为群 (G,*) 的阶，记为 |G| 。
有限群&无限群： 如果 |G| 无限大，则称这个群为无限群，否则是有限群。
打个比方，上面的 (Z,+) 这个群就是无限群，有限群的例子下面有。
置换
定义
我们一般描述成这样：
\left(
\begin{matrix}
1 & 2 & 3 & ... & n-1 & n\\
a_1 & a_2 & a_3 & ... & a_{n-1} & a_n
\end{matrix}
\right)
其中 a 是 1 ~ n 的一个排列，这个置换表示将位置 1 上的元素放到位置 a_1 ，位置 2 上的元素放到 a_2 ……
由于其中涉及到 n 个元素，所以称其为 n 元置换。
举个例子，假设有一个置换 T ：
\left(
\begin{matrix}
1 & 2 & 3 & 4\\
4 & 3 & 1 & 2
\end{matrix}
\right)
对于序列 A=(4,3,2,1) ，将 T 作用在 A 上，得到 A'=(2,1,3,4) 。
可以发现，将列进行调换不影响答案，比如说可以将上面的置换 T 改成：
\left(
\begin{matrix}
2 & 4 & 3 & 1\\
3 & 2 & 1 & 4
\end{matrix}
\right)
将这个形式的 T 作用在 A 上依然能得到 A' ，原因显然。
连接
这是关于置换的运算，对于置换 A,B ，AB 即表示 A 和 B 的连接运算。
连接运算的规则是这样的：
\left(
\begin{matrix}
a_1 & a_2 & a_3 & ... & a_n\\
b_1 & b_2 & b_3 & ... & b_n
\end{matrix}
\right)
\left(
\begin{matrix}
b_1 & b_2 & b_3 & ... & b_n\\
c_1 & c_2 & c_3 & ... & c_n
\end{matrix}
\right)=
\left(
\begin{matrix}
a_1 & a_2 & a_3 & ... & a_n\\
c_1 & c_2 & c_3 & ... & c_n
\end{matrix}
\right)
循环
对于一个 n 阶循环 (a_1a_2a_3...a_{n-1}a_n) ，它表示这样一个置换：
\left(
\begin{matrix}
a_1 & a_2 & a_3 & ... & a_{n-1} & a_n\\
a_2 & a_3 & a_4 & ... & a_n & a_1\\
\end{matrix}
\right)
对于一个置换，我们可以将其表示为若干个不相交循环的乘积（并不是乘法的乘积，感性理解一下就好）。
比如说，对于这个置换：
\left(
\begin{matrix}
1 & 2 & 3 & 4\\
3 & 2 & 1 & 4
\end{matrix}
\right)
就可以表示成 (1~3)(2)(4) 。
证明很显然，这里不赘述了。（不懂的话可以去做这题 找不到其他有这题的网站了……）
置换群
置换群就是由置换组成的群，运算就是连接。
举个例子，假设有一个正方形，四个顶点染了色，可以旋转或翻折。那么置换就有 8 种：
不动，顺时针转 90\degree,180\degree,270\degree ， 4 种
以两条对边的中点为轴翻转 180\degree ，有 2 组对边
以两个对点为轴翻转 180\degree ，有 2 组对点
显然，这 8 个置换可以组成一个置换群，由于这些置换包含了所有的置换方式，所以肯定满足封闭性 ，连接运算显然满足结合律 ，单位元 就是不动，逆元 就是反着操作。
以及，这是一个有限群。
陪集
设 H 为 G 的一个子群（也需要满足上面 4 点限制），a\in G ，那么 aH 称为 H 的左陪集，Ha 称为 H 的右陪集。（注意，陪集不是群，不需要满足 4 点限制）
其中，aH=\{ax|x\in H\},Ha=\{xa|x\in H\} 。
下面性质的证明都只考虑左陪集，因为右陪集的证明是基本一样的。
性质1
如果 a\in H ，那么 aH=H 。
证明很显然，因为 H 内已经有 a 了，根据封闭性，对于任意 b\in H 都存在 (a*b)\in H ，所以 aH 不会比 H 多出任何元素。
性质2
H 的所有陪集的大小都等于 |H|
对于一个陪集 aH ，假如 a\in H ，那么根据性质 1 ，可以得到 |aH|=|H| 。
假如 a\not\in H ，那么 aH \cap H=\empty ，且 aH 内没有相同的元素，根据陪集的定义，显然有 |aH|=|H| 。
性质3
如果 b\in aH ，那么有 bH=aH 。
因为 b\in aH ，所以 b 可以表示为 a*x ，所以 bH=a*xH=aH 。
性质4
根据性质 3 ，可以得到这样的推论：如果 aH\cap bH\ne \empty ，那么 aH=bH 。
证明很显然，设 c\in (aH\cap bH) ，那么就有 bH=cH=aH 。
拉格朗日定理
对于有限群 G 的任意子群 H ，都有 |H|||G| 。
人话翻译：G 的阶是 H 的阶的倍数。
不要被拉格朗日吓到了，证明不难。
首先有一个结论：H 的所有陪集的并集等于 G 。证明很显然。
又因为，H 的陪集 aH 要么满足 H=aH ，要么满足 H\cap aH=\empty ，所以可以将 G 划分为若干块，每一块是 H 的一个陪集，根据性质2 ，每一块的大小都是 |H| ，所以 |H|||G| ，以及 \frac {|G|} {|H|} 就等于块数。
以及，下面都只考虑有限群。
轨道-稳定集定理
这个定理主要用来辅助证明burnside定理。
首先给两个定义：
对于一个状态 k ，将置换群 G 作用在 k 上，所有能够转移到的状态记录在集合 E_k 中，我们称 E 为等价类，E_k 是 k 所在的等价类
对于一个状态 k ，假如一个置换 T 作用在 k 上依然得到 k ，那么将 T 记录在 Z_k 中，Z_k 表示作用在 k 上依然得到 k 的置换的集合。
轨道-稳定集定理：
对于任意状态 k ，都有 |E_k|\times |Z_k|=|G| 。
先给个例子理解一下，就用百度百科上的正方形顶点二着色问题：
一共有 4 种置换：不动，旋转 90\degree,180\degree,270\degree ，显然他们可以组成一个置换群 (G,连接) 。
这里没有像上面一样考虑翻折操作，因为这里只需要这四种置换就能组成置换群，换言之，在这题中任意翻折操作等价于某个旋转操作。（你可以试试看，对于任意状态 a ，假如翻折能得到状态 b ，那么 a 通过旋转也一定能得到状态 b ）
考虑状态 2 ，在 G 的作用下能得到的状态有 E_2=\{2,3,4,5\} ，作用在状态 2 上依然得到状态 2 的置换只有不动，即 |Z_2|=1 ，又因为 |G|=4 ，所以有 |E_2|\times |Z_2|=|G| 。
再看状态 1 ，在 G 的作用下能得到的状态有 E_1=\{1\} ，作用在状态 1 上依然能得到状态 1 的置换有 4 种（显然状态 1 怎么转都不变），即 |Z_1|=4 ，也满足 |E_1|\times |Z_1|=|G| 。
虽然可能是多嘴但还是说多一句：对于任意 l\in E_k ，都有 E_l=E_k 以及 Z_l=Z_k ，原因挺显然的，不明白的可以结合下面的证明来理解。
轨道-稳定集定理 证明：
首先，Z_k 其实是 G 的一个子群，因为它包含了所有作用在 k 上不变的置换，所以满足封闭性 ，连接运算满足结合律 ，逆元 就是反着操作，由于顺着操作不会变，所以反着操作也不会变，所以反着操作这个置换也一定在 Z_k 中，单位元就是不动，很显然不动这个置换一定在所有 Z 里面。
再看 E_k 中的状态，对于一个状态 p(p\ne k) ，从 k 转移到 p 一定要用到一个 Z_k 以外的置换 a ，那么就存在一个 Z_k 的陪集 aZ_k ，且 Z_k\cap aZ_k=\empty 。
结合性质 3 以及在拉格朗日定理中提到的将 G 进行分块，我们知道，对于任意 b\in aH ，都有 bH=aH ，也就是说，在 G 中有 |H| 个置换可以将 H 变成陪集 aH ，且 aH=H ，不妨称这些置换为本质相同的置换，显然的，有 \frac {|G|} {|H|} 个本质不同的置换。
可以发现一个性质 P ：对于状态 k ，一类本质相同的置换 b\in aZ_k 作用在 k 上时，得到的新状态 K 都是相同的。证明很显然，所有本质相同的 b 都可以表示为 a*x （* 是连接运算），所以 b 作用在 k 上 等价于 先让 x 作用在 k 上，再让 a 作用在 k 上，由于 x\in Z_k ，所以 x 在 k 上作用完后依然得到 k ，所以所有 b\in aH 在 k 上作用都等价于 a 在 k 上作用。
此时，k 一共可以置换到 |E_k| 种状态，根据性质 P ，我们可以知道，这说明在所有置换中，有 |E_k| 种本质不同的置换，于是得到 |E_k|=\frac {|G|} {|H|} ，移项即得到 |E_k|\times |H|=|G| ，而在这里，H 就是 Z_k ，于是得证 。
burnside定理
这才是 OI 中群论的重头戏，基本上题目都是用到这个定理来解决。（顺便提一句，P\acute olya 定理的本质就是burnside定理）
还是要先说一个定义：在上面我们知道，对于一个状态 k ，存在一些置换 Z_k ，满足 Z_k 中的置换作用在 k 上时依然得到 k ，设 T\in Z_k ，那么我们称 k 是 T 的不动点。显然，一个置换可以有多个不动点，设 c(f_i) 表示置换 f_i 的不动点数。
为了方便，设群 (G,*) 作用在状态 [1,n] 上，满足 G=\{f_i|i\in[1,n]\} ，其中 f_i 是一个置换，以及设 S 表示所有状态形成的等价类数量。
burnside定理：
S=\frac 1 {|G|}\sum_{i=1}^{|G|} c(f_i)
有了轨道-稳定集定理 ，这个东西证明起来真的太容易了。
先看后面的 \sum_{i=1}^{|G|} c(f_i) ，即所有置换的不动点数量之和，换一个角度来求这个东西，它等于 所有等价类的 |E|\times |Z| 之和，因为 E 中所有状态都是 Z 中任意置换的不动点。而每个等价类的 |E|\times |Z| 都等于 |G| 。所以所有等价类的 |E|\times |Z| 之和就等于 S\times |G| 。
带入到上面的柿子，很显然等式成立了。
这个东西要应用到题目里的话，一般题目会要求出本质不同的方案数，而本质相同的方案之间一般可以通过旋转或翻折等方式得到，我们将这些操作作为置换，构成置换群，将其作用在所有方案上，可以得到若干个等价类，一个等价类里的方案都是可以通过置换相互得到的，这表明他们都是本质相同的方案，所以本质不同的方案数就是等价类数，用burnside定理求出来即可。
P\acute olya 定理再次声明，这只是burnside定理的一个具体使用方式，要做更广泛的题还是要用burnside定理。
以及，回顾一个有点久远的知识点：每个置换可以表示成若干个循环的乘积。
P\acute olya 定理：
设 G=\{f_1,f_2,...,f_{|G|}\} 是作用在 [1,n] 上的置换群，给 [1,n] 进行染色，有 col 种颜色，则总方案数为 col^n ，对于置换 f_i ，设 m(f_i) 表示置换 f_i 可以拆成多少个循环的乘积，那么在 G 的作用下，[1,n] 的等价类数量为
\frac 1 {|G|}\sum_{i=1}^{|G|} col^{m(f_i)}
其实，里面的 col^{m(f_i)} 就等价于burnside定理中的 c(f_i) ，即不动点数量，因为 f_i 可以拆成 m(f_i) 个循环，而每个循环内要保持不动的话必须要求每个状态的颜色都相同，一共有 m 中颜色可以选择，而两两循环间的颜色互不相关，所以总不动点数就是 col^{m(f_i)} 。
例题
更多练习题的话，给大家安利这份题表。