群论小记

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

$1.\forall a,b∈G, a*b∈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!$ 个置换构成的集合，关于置换操作就成群了。

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

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

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

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

$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$ 下不变的元素个数

就一句话 $|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

很有趣的置换