置换群

顾名思义，由置换作为元素的群，(n=mid Smid),n称为置换群G的阶,G中有(n!)个置换

一个置换群中的性质:

1.封闭性:两个置换，即映射，他们的运算结果也是一个等阶映射。

注意，(1 2)之类的不完整循环仅仅是缩写，只表示其他元素直射，不要误认为他们不等阶

2.结合律:(p1*(p2*p3)=(p1*p2)*p3)一样成立

3.单位元:e表示所有元素直射

4.逆元:就是p的反射，对于一个由对换的积表示的p

(p=(a1space a2)......(akspace an))

则(p^{-1}=(akspace an)......(a1space a2))

置换群的重要之处在于任意有限群都与置换群同构，置换群通过元素之间的映射表示变换，即可以表示一切有限群

一个置换分解为对换积的奇偶性成为该置换的奇偶性，一个群中奇偶置换的个数相等，等于(1/2*n!)

轨道:在G中，所有k可以映射到的点集被称为轨道，(E_k)，又称等价类

稳定化子:在G中，所有k为直射的置换的集合被称为稳定化子，(Z_k),并且其为G的子群

(mid Z_kmid*mid E_kmid=mid Gmid)

Burnside引理

G是(N={1,2......n})上的置换群，G在N上可引出不同的等价类，并且其个数为

(l=mid Gmid^{-1} *Sigma^{g}_{i=1}c_1(a_i))

burnside引理的严格证明较复杂，在此略去，只谈一下我的理解

对于同一个等价类，其中所有元素会保持在一个置换中保持相同的性质，即都作为不动点或都不作为不动点

关于这个公式，直接看肯定有不理解之处，只能在实践中体会

举一个例子,求n个不同的人围成一桌的方案数

首先，我们知道这是个圆周排列，方案数为((n-1)!)

用burnside引理的角度，一共存在(n!)种方案，对于每一个方案，存在((n-1))个与其循环同构的置换

并且这(n)个循环同构的置换贡献总共为1

考虑这组置换中的每一个点，由于每一个点权重相等，且这组没有本质区别的置换每一次循环的格式相同

可以把贡献分摊在每一个点上，看成每一个点贡献为1，由于权重相等，这组置换的贡献为n，去重后为1

这个题非常简单，但是它揭露了几个性质:

1.每个点权重相等，即在统计时不会因为置换的原因而改变贡献

2.burnside引理要列举每一个状态，时间复杂度实际上是阶乘级的

3.最关键的步骤在找同构。这个题中由于是圆周，体现为循环

先写到这里，后面会陆续找一些例题来分析(咕咕咕