置换群、Burnside引理与等价类计数问题

标签：置换群 Burnside引理

置换

说说我对置换的理解，其实就是把一个排列变成另外一个排列。简单来说就是一一映射。而置换群就是置换的集合。

比如\[ \left(\begin{array}1
1 & 2 & 3 & 4 & 5 \\
5 & 3 & 4 & 2 & 1
\end{array}\right) \]是一个置换。也可以把置换看做定义域和值域都为{1,2,......,n}的函数，我们通常把置换写成形如{\(a_1,a_2,a_3,......,a_n\)}的形式，代表置换\[ \left(\begin{array}1 1 & 2 & 3 & ...... & n \\ a_1 & a_2 & a_3 & ...... & a_n\end{array}\right)\]

置换之间可以进行乘法。如置换f={3,1,4,2},g={2,3,4,1},那么fg={4,2,1,3}。而且置换乘法满足结合律，不过置换乘法并不满足交换律。如上面的例子，gf={1,4,2,3}。

为了方便我们处理置换，我们还经常把置换表示成循环的乘积。循环是什么呢?\(\left(\begin{array}1 1 & 2 & 3\end{array}\right)\)相当于置换\(\left(\begin{array}1 1 & 2 & 3\\2 & 3 & 1\end{array}\right)\)。一个循环就像一个环，其中每一个元素向下一个元素连边。由于每个点的出度与入度都为1，任意置换都能被分解为若干个循环。我们称一个置换中循环的个数为循环节，对于不相交的循环相乘是满足交换律的。

等价类计数问题

在这种题目中，题目会定义一种等价关系。满足等价关系的两种元素被看成同一种元素。这样就可以把这些元素分为很多个等价类，等价类中的元素相互等价。通常题目会让你求出等价类的个数。怎么来解决这种类型的问题呢?接下来我们引入Burnside引理。

Burnside引理

设置换群G为等价关系集合，且对于任意\(f,g\in G,都有fg\in G\) 。
记C(f)为经置换f作用后不动点的个数。则等价类个数L满足\[L=\frac{ \sum_{f \in G} {C(f)} }{|G|}\]

证明：
设\(Z_k\)为使k为不动点的置换集合，\(E_k\)为元素k所在的等价类。
\[ \sum_{f \in G} C(f) = \sum_{i=1}^n Z_i \]
而\[ \sum_{i=1}^n Z_i =\sum_{i=1}^L |E_i||Z_i| \]
又\[\because |Ei||Zi|=|G|\]
\[\therefore \sum_{i=1}^L |E_i||Z_i|=L|G|\]

我的理解是：
每一个置换的不动点个数之和就是使每一个元素不动的置换个数之和，所以\[ \sum_{f \in G} C(f) = \sum_{i=1}^n Z_i \]
而同一个等价类中使一个元素不动的置换个数相等，所以\[ \sum_{i=1}^n Z_i =\sum_{i=1}^L |E_i||Z_i| \]

又由轨道-稳定集定理，即“轨道大小×稳定化子数=变换个数”，（具体证明可以参照《组合数学》（第5版）P181 定理4-11），所以\[ \sum_{i=1}^L |E_i||Z_i|=L|G|\]

至于Polya定理的证明很容易用Burnside引理解决，这里不再赘述。