有一天,我发现自己不会群论

群论前置知识

群:称一个集合和定义在上的一个二元运算构成一个群,当且仅当运算满足:

结合律、单位元存在、逆元存在、运算封闭性。

 

子群:对于集合的一个子集,运算对于上述性质依然成立,则称的一个子群。

 

陪集:

鉴于群运算不一定有交换律,所以分为左陪集和右陪集。

的一个子群,
是H的左陪集,的右陪集。
由于逆元存在,所以
陪集不一定是群,并且陪集是群当且仅当,证明如下。

显然当时,由群的定义可以知道是一个群。

我们只需要证明必要性,也就是证明下面的问题。

假设并且的子群,那么有

显然

假设属于,那么因为也属于,所以两者乘起来可以得到矛盾。

故当一定不是群。

 

拉格朗日定理:若的子群,则的约数。证明如下。

对于两个元素,有

假设,那么存在

那么,于是

因为,所以

所以

故是两个不同的左陪集无交。

于是的不同陪集个数

的约数。

 

置换:有限集合到自身的一一映射称为一个置换

 

有限群:集合由有限个元素组成的群称为有限群(为了方便,以下群若无特殊说明均指有限群)

 

置换群:置换组成的群称为置换群

有限集的所有置换个数为

 

轨道与等价类

原数列集合中的元素,在置换群中所有置换的像构成的集合叫做的轨道或者包括的等价类,记作

 

稳定子集与稳定化子:

有限集中某个元素构成了的一个子集,置换群中可以使中所有元素不动的置换构成的子群叫做的一个稳定子群,又称稳定子集或稳定集。

时,也就是有限集中的元素,置换群中可以使元素不动的置换构成的子群,记为,我们也称其为的稳定化子。

 

轨道-稳定化子定理:对于一个置换群和一个元素 证明如下

显然,由于

的一个子群。

我们考虑所有置换,有

由于所有不同的组成的集合为,所以所有不同的左陪集数为

由拉格朗日定理,所有不同的左陪集数即可得证。

 

置换的不动点:对于置换,集合中满足的点

 

Burnside 引理

是目标集上的置换群,表示在置换作用下的不动点个数。

划分成个等价类,那么:

证明如下。

由于每个轨道对答案贡献为,所以每个元素对答案的贡献为

由轨道-稳定化子定理

 

Pólya定理

由Burnside 引理我们可以得到Pólya定理。

是目标集上的置换群,设是以目标集的排列为元素的集合。

表示在置换的作用下循环节的个数。如果中颜色分别进行染色,然后把划分为个等价类,那么