群论小记

· · 个人记录

首先我们来说明一下什么是群。给定一个集合 G={a,b,c,\cdots} 和集合 G 的二元运算 *，并满足

$2.\forall a,b,c, a*(b*c)=(a*b)*c$ （结合律） $3.\exist e\in G,\forall a\in G, a*e=e*a=a$（存在单位元） $4.\forall a, \exist a^{-1}\in G,aa^{-1}=a^{-1}a=e$ （存在逆元） 注，$*$ 运算可以不满足交换律。但是交换律一定要对单位元和逆元满足！ 这样，我们就称集合 $G$ 在运算 $*$ 下成群，记作群(一个字母) $=(G,*)

话说这里的G应该是group的缩写

聊一聊对于群(G,*)的一些性质

1.$ 若 $a,b,c \in G,a*b=c*b$，则 $a=c

证明：两边同时乘上 b^{-1}，在运用结合律和单位元的性质即可

推论一：对于任意 x\in G，有且仅有一个 y\in G，使得 xy=yx=x。且这个 y 一定是 e（反证法即可）

顺便提一嘴，如果 a*b\neq c*b，那么 a\neq c，这是 a=c 则 a*b=c*b 的逆否命题。

2.$ 对于群 $G$ 中任意一个元素 $x$，有且仅有一个逆元 $x^{-1}

其实就是证明不可能同时有两个，那就反设它有两个逆元 a,b。然后就有 ax=bx=e，从而 a=b。本来 a 和 b 打得不可开交，结果发现是自己人，尴尬收场。

我记得当初还证明过几个的，但是忘掉了。

接下来我们聊聊置换

置换，它是一个操作，对象是序列（可以有重复的元素），可以用一个序列或者用循环表示法表示。（下文要用到循环表示法，请读者自行查阅如何使用它）

它把 i 替换成了在 p_i 的元素（ p 应当是一个排列）

显然对一个长度为 n 的序列，有 n! 种置换的方案。那么，对于这些置换所构成的集合，在置换的意义下到底成不成群呢？

封闭性显然。

结合律的话，我们用两行的那种表示方法，表示第二第三个置换，然后我们改变一下列与列之间的顺序，使置换二的第一行和置换一的第二行一致，置换三的第一行等于置换一的第二行，然后操作等价于消去中间四行，并把剩下两行并在一起。如此观之，结合律也是比较显然的

单位元可以构造。

逆元的话，我们把改变列与列之间的顺序，使置换的第二行变为 1,2,\cdots,n，然后再把换到第一行，对应的就是逆元了！

这样由 n! 个置换构成的集合，关于置换操作就成群了。

注：网络上有的置换群指的是我这里置换群的子群。其实置换群应当是按我这个定义来的，但是奈何很多人没有系统学过群论，定义只能因人而异了。

接着，我们来研究一下群论相关计数问题。这种类型的题。一般来讲，一个物品/矩阵/集合所有的状态会先告诉你，但是会给你描述一种或几种变换，如果一个状态能通过这几种变换（一次或多次），能够到达另外一个状态。那么就认为这两个状态“本质相同”。最后往往是问你“本质不同”的状态个数。

注意，这里（包括下文）所述的“状态”可以有等价的情况！

这里我们先来声明一下各个变量的名称极其意义。

$s$：**置换**个数 $Z_k $：$k$ 不动置换类，又称 $k$ 的稳定集。是一个集合，这里的 $k$ 表示的是一个状态。它储存了所有**置换**，which 作用在 $k$ 上仍使其保持该状态 $E_k$：$k$ 的等价类，又称 $k$ 的轨道。$k$ 仍指状态，储存的是状态 $k$ 经过置换群子群 $G$ 的作用下能到达的所有状态。 $N$：表示所有等价类 $E_i$ 总的集合。形式化地讲，$N=E_1+E_2+\cdots+E_L$。请注意，本文会用 $L$ 表示本质不同的状态个数（也就是最后所要求的答案） $D(a_j)$：表示在置换 $a_j$ 下不变的元素个数 $S_{i,j}

轨道稳定集定理

就一句话 |E_k||Z_k|=|G|

这个定理比 Burnside 和 Polya 都重要。这是 Mike 大大的原话。确实，该定理之于它们，就像 C++ 对 Python，Scratch等语言的作用一样。

证明：

首先根据 E_k 的定义，对于任意一个在 E_k 中的元素 x，我们一定能至少找到一个 op \in G，满足 k*op=x

然后捏，根据 Z_k 的定义，我们能找到 |Z_k| 个操作op_1,op_2,\cdots,op_k，使得 k*op_i=k

注：这里并没有和上文那个“推论”产生矛盾，因为这里变到自己的元素并不在群 G 里，而是一个状态。对于一个状态，可以存在多个在 G 里的元素，使得这个状态仍然回到自己本身。

那么对于 E_k 的第 i 个元素 x，我们有 op \in G, k*op=x，我们就能构造出一组操作 op_1*op,op_2*op,\cdots,op_{|Z_k|}*op（注：这里 op_i 和 op 的顺序同样有讲究，在这里 op_i 在前面的原因是，用一次结合律，先让状态 k 变到自己，再使其通过 op 变到 x。这样发出的组合拳才是有力的）

如上，我们便证明了 |E_k||Z_k|\leq |G|

如何证明 |E_k||Z_k|\geq |G| 呢？

我们发现，如果该定理成立，最后能使 k 变到 x 的置换数一定是 |Z_k| 个。

那么我们运用反证法，如果说能使 k 变到 x 的置换数一定是 |Z_k| 个。我们把所有的置换给列出来 op_1,op_2,\cdots,op_m,m>|Z_k|，根据群的性质，它们一定存在对应的逆 op_1^{-1},op_2^{-1},\cdots,op_m^{-1}，我们发现 \{op_1*op_1^{-1},op_1*op_2^{-1},\cdots,op_1*op_m^{-1}\}\subseteq Z_k，并且根据推论一，这个集合里没有相等的元素。最后得到 |Z_k|\geq m，矛盾！

综上，我们证明了 |E_k||Z_k|=|G|

接下来，我们维护一个量，如果状态 i 在置换 j 下不变的话，那么这个量加 1

交换求和号会发现 \sum\limits_{k=1}^n|Z_k|=\sum\limits_{j=1}^sD(a_j)

从而 \sum\limits_{j=1}^sD(a_j)=\sum\limits_{k=1}^n|Z_k|=\sum\limits_{k=1}^n\frac{|G|}{|E_k|}=|G|\sum\limits_{k=1}^n\frac{1}{|E_k|}=|G|\sum\limits_{i=1}^L\sum\limits_{k\in E_i}\frac{1}{|E_k|}=L|G|

有 L=\frac{1}{|G|}\sum\limits_{j=1}^sD(a_j)

这便是 Burnside 定理！

但是我们要看右式，这个定理需要遍历所有的 s 个置换，如果置换数太多怎么办？

对于置换 a_j，用循环表示法表示成 c(j) 个诸如 (h_1,h_2,\cdots,h_k) 的形式。

如果该状态对 D(a_j) 有贡献的话，那么一定要满足同一个循环内的 h 要全部一样，对吗？

假设对于第 i 个循环，里面的 k 个元素决策集合分别是 S_1,S_2,\cdots,S_k，那么很显然第 i 个循环有 |\bigcap\limits_{i=1}^kS_i| 种方案。

那么 D(a_j)=\prod\limits_{l=1}^{c(j)}|\bigcap\limits_{i=1}^kS_i|，代入到 Burnside 定理就成了 Polya 定理！

怎么样，是不是想做两题摩拳擦掌了？

1.瓷砖染色

如何判定置换群完整？其实就是不断添加元素，最后封闭了即可。

e,r,f

2.spoj

很有趣的置换