群论入门
jun头吉吉
·
·
个人记录
在 数数入门 也 copy 了一份，不过有点卡，所以单独开一篇
群
定义
定义集合 G 和二元运算 \times ，记为 (G,\times)，满足以下条件的称为群：
- 封闭性：\forall a,b\in G,a\times b\in G
- 结合律：\forall a,b,c\in G,(a\times b)\times c=a\times(b\times c)
- 单位元（幺元）：\exists e\in G,\forall a\in G,a\times e=e\times a=a
- 逆元：\forall a\in G,\exists a^\prime\in G,a\times a^\prime=a^\prime\times a=e，不难证明逆元唯一
子群
若 H 为 G 的一个子集，且 (H,\times) 构成一个群，那么称 H 为 G 的一个子群，记作 H\leq G
如果 g\in G
陪集的性质（以右陪集为例）：
-
\forall g\in G,|H|=|Hg|
证明：因为逆元唯一，如果 h_1\not=h_2 ，而且 h_1\times g=p=h_2\times g ，那么 h2=p\times g^\prime=h_1 ，矛盾，因此 h_1\times g\not=h_2\times g
-
\forall g\in G,g\in Hg
证明：H 是群，H 内一定存在一个单位元 e 满足 e\times g=g ，因此 e\times g\in Hg\Leftrightarrow g\in Hg
-
Hg=H\Leftrightarrow g\in H
证明：假设 g\not\in H ，eg\not\in Hg，矛盾
-
Ha=Hb\Leftrightarrow a\times b^{-1}\in H
证明：由性质 3 可得
-
Ha\cap Hb\not=\varnothing\Leftrightarrow Ha=Hb
证明：假设 c\in Ha,c\in Hb，\exists h_1,h_2 满足 h_1\times a=c,h_2\times b=c,a\times b^{-1}=h_1\times h_2^{-1}\in H ，用性质 4 可以得到。
-
H$ 的全体右陪集的并为 $G
证明：因为 H 存在单位元 e，g 取遍 G 中的每个元素。
一些表述
如果 H\le G ：
H/G$ 表示 $H$ 的所有左陪集 $\{gH|g\in G\}
## 拉格朗日定理
**拉格朗日定理**：对于有限群 $G$ 与有限群 $H$，若 $H$ 为 $G$ 的子群，那么有： $|H|\text{整除}|G|
即 H 的阶整除 G 的阶。
更具体点：|H|\times [G:H]=|G|
证明：陪集大小和为 |G| ，陪集大小为 |H|，那么 [G:H]=\frac{|G|}{|H|}
置换群
设 N=\{1,2,\ldots,n\}，令 M 为 N 的一个排列（一个置换），然后定义两个置换 A 与 B 的 \times 操作得到一个新的置换 C 满足 C_i=B_{A_i}，让集合群 G=(M,\times)。
循环：置换 \begin{pmatrix}a_1&a_2&\ldots&a_{n-1}&a_n\\ a_2&a_3&\ldots&a_n&a_1\end{pmatrix} 称为 n 阶循环，记为 (a_1\ a_2\ \ldots\ a_{n-1}\ a_n)。不难发现任何一个置换都可以写作几个循环的乘积，并且结果唯一。
「群作用」：对于一个集合 M 和群 G，若给定了一个二元函数 \varphi(v,k) 其中 v 为群中的元素，k 为集合元素，且有 \varphi(e,k)=k，\varphi(g,\varphi(s,k))=\varphi(g\times s,k) ，则称群 G 作用与 M
轨道-稳定子定理
轨道：作用在 X 上的置换群 G。X 中的元素 x 的 轨道 是在群 G 的作用下能够转移到的元素集合。x 的轨道被记为 G(x)，g(x) 表示群 G 元素 g 作用于 x 的群作用的返回值，即 g(x)=\varphi(g,x)。
稳定子：G^x=\{g|g(x)=x,g\in G\}
轨道-稳定子定理：|G^x||G(x)|=|G|
证明：由拉格朗日定理可以得出 |G^x|[G:G^x]=|G|，因此只需要证明 [G:G^x]=|G(x)|
如果 f(x)=g(x)，那么 f(x)g(x)^{-1}=e(x)\in G^x。由于陪集的性质 fG^x=gG^x。因此 fGx=gG^x\Leftrightarrow f=g。
于是让 gG^x 对应 g 就可以不重不漏地表示所有陪集。
\rm Burnside 引理
公式：定义 G 为一个作用于 X 置换群，如果 x,y\in X 在 G 的作用下可以相等即存在 f\in G 使得 f(x)=y 则定义 x,y 属于一个等价类，则不同的等价类数量为：
|X/G|=\frac1{|G|}\sum_{g\in G}X^g
其中 X^g 为 X 在 g 的作用下的不动点数量，即满足 g(x)=x 的 x 的数量。
由于每个元素属于仅属于一个轨道，轨道内部在群 G 作用下互达，所以我们可以得到：
|X/G|=\sum_{x\in X}\frac1{[G:G^x]}
根据轨道-稳定子定理，得到：
[G:G^x]=\frac G{|G^x|}
|X/G|=\sum_{x/in X}\frac{G^x}{G}
|X/G|=\frac1{|G|}\sum_{x\in X}G^x
反过来，就是对于每一个群作用 g ，其作用下不动点的数量。
\rm Pólya 定理
对于一个置换 (a_1,a_2,\ldots,a_n)。
在使用 \rm Burnside 解决染色问题的时候，我们需要求的是不动点的数量，而对于上述的置换，假设我们令每个 i 向 a_i 连一条边容易发现会得到若干个环，仔细思考，每个环的颜色应当相同。
我们定义这个环的数量为 c(g) 即置换 g 的轮换(环)数。
那么我们现在可以改写 \rm Burnside 定理为：
\frac1{|G|}\sum_{g\in G}m^{c(g)}
一些例题
例题1：P4980 【模板】Pólya 定理
考虑置换群 G，有顺时针旋转 0,1,\ldots,n-1。旋转 i 格轮换为 \gcd(i,n)，先给一个比较丑的证明：
假设一个点在 p，旋转 k 次，每次 x 格后回到原点，有：
\begin{aligned}
&p+kx\equiv p\pmod n\Rightarrow kx\equiv 0\pmod n\\
&x|kx\quad \&\quad n|kx\Rightarrow kx=\operatorname{lcm}(x,n)=\frac{nx}{\gcd(n,x)}\\
&\large k=\frac{n}{\gcd(n,x)}
\end{aligned}
一共有 n 个数，每 \frac n{\gcd(n,x)} 个数构成一个环，共 \gcd(n,x) 个环。
于是直接上 \rm Pólya 定理
\begin{aligned}
&\frac1n\sum_{i=1}^nn^{\gcd(i,n)}\\
&=\frac1n\sum_{d=1}^nn^d\sum_{i=1}^n[gcd(i,n)==d]\\
&=\frac1n\sum_{d|n}n^d\sum_{i=1}^{\frac nd}[\gcd(i,\frac nd)==1]\\
&=\frac1n\sum_{d|n}n^d\varphi(\frac nd)
\end{aligned}
例题2：P2561 [AHOI2002]黑白瓷砖
设点的总数为 N=\frac{n\times(n+1)}{2}
考虑置换群 G:
- 不动，显然轮换数为 N
- 旋转 120\degree,240\degree，轮换数为 \lceil\frac N3\rceil
- 沿三条对称轴翻转，对称轴上有 \lceil\frac n2\rceil 个点，轮换数为 \frac{N-\lceil\frac n2\rceil}{2}+\lceil\frac n2\rceil
于是得出答案：
\frac16(2^N+2\times2^{\lceil\frac N3\rceil}+3\times2^{(\frac{N-\lceil\frac n 2\rceil} 2+\lceil\frac n2\rceil)})
例题3：SP419 TRANSP - Transposing is Fun
如果一个数为 \overbrace{X}^a\overbrace{Y}^b，那么他将和 \overbrace{Y}^b\overbrace{X}^a 交换位置。朴素地交换是 2^{a+b} 的，是什么让它少了？举个简单的例子：a=2,b=1
0&1\\
2&3\\
4&5\\
6&7
\end{pmatrix}\Rightarrow
\begin{pmatrix}
0&4\\
1&5\\
2&6\\
3&7
\end{pmatrix}
写出置换：
0&1&2&3&5&6&7\\
0&2&1&5&6&5&7
\end{pmatrix}=(0)(12)(356)(7)
每个循环内交换。设循环大小为 x，那么只需交换 x-1 次。若最终由 K 个循环，就少交换 K 次，答案为 2^{a+b}-K
只需求出多少个循环即可。一个循环内的数有什么特点。由一开始的定义，他们都可以通过多次循环左移 a 位得到。（叫循环左移是因为要把高 a 位移到最低位）。
于是转化问题：一个 a+b 个珠子的环，可以染两种颜色。两个环通过若干次顺时针旋转 a 格得到的称为等价类。问有多少个等价类。等价类的数量就等于上面说的循环个数。
不过这个转 a 格与我们上面的问题略有不同。显然会有 \gcd(a,a+b)=\gcd(a,b) 个循环节，每个循环节互不影响。于是再转化：有 \frac{a+b}{\gcd(a,b)} 个大珠子，每个大珠子有 2^{\gcd(a,b)} 种染色方案。两个环若干次旋转一格能够相等称为同构，求数量。
直接上 \rm Pólya 即可，推导与上面类似，设 n=\frac{a+b}{\gcd(a,b)}直接给出最终答案：
2^{a+b}-\frac{1}{n}\sum_{d|n}2^{gcd(a,b)\times d}\times\varphi(\frac nd)
SP422 TRANSP2 - Transposing is Even More Fun 用类似的方法也能过。
例题4：P4128 [SHOI2006] 有色图
说好的有色图呢
设颜色数量为 k
我们前面都是点置换，现在变成了边置换。
点置换的数量是 n! 显然不可以直接枚举。考虑一个数列 a_1,a_2,\ldots,a_m 满足 \sum\limits_{i}a_i=n 且 a_i≥a_{i-1}，其中 a_i 表示第 i 个循环节的大小，那么一个数列 a_i 与对应着若干点置换。
更具体的，若 cnt_x 表示 a_i=x 的数量，这个数列对应 \displaystyle\frac{n!}{\prod_ia_i\prod cnt_x} 个点置换。他们边置换的轮换数都是一样的。
那么每个循环贡献的不动点数量为 \lfloor \dfrac {a_i} 2 \rfloor
两个循环贡献的不动点数量为 \gcd(a_i,a_j)
最后对答案的贡献为：
\frac{1}{|G|}\times\dfrac{n!}{\prod a_i \prod \dfrac{x}{cnt_x}}k^{\sum_{i=1}^m\lfloor \frac {a_i} 2 \rfloor+\sum_{1\le i<j\le m} \gcd(a_i,a_j)}
我们知道 |G|=n!，于是还可以消掉一些东西。
数列 a 的数量不会很大，具体可以参见 OEIS
P4727 [HNOI2009]图的同构计数 就是 k=2 的情况