置换

置换（permutation）是群论中研究对称群的工具。

元素

群$S_n$表示$S = \{ 1,2,\cdots,n \}$上所有双射的全体，其中的一个元素$\sigma \in S_n$可以写为 $$\sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}$$ 例如$\sigma' = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 1 & 2 & 5 & 4 & 6 \end{pmatrix} \in S_6$，该映射将1映成2，将2映成3等等。

很多情况下为了简化，我们会采用循环群的群作用来表示一个对称群中的元素$\sigma.$

循环

假设$\sigma \in S_n$生成的一个循环群$\langle \sigma \rangle$，让这个群左乘作用在集合$S = \{ 1,2,\cdots,n \}$上，这个作用的轨道形成了$S$的一个分划（partition），这也就是说，每一个$\sigma$都唯一确定了集合$S$上的一个分划，例如上面的例子$\sigma'$就将$S$分为了$\{ \{ 1,2,3 \}, \{ 4,5 \}, \{ 6 \} \}.$因此我们可以将一个元素按照轨道划分分别研究每个轨道，再研究整体。这促使我们给出如下定义：

设$\sigma \in S_n$，如果$\sigma$形成的循环群$\langle \sigma \rangle$作用在集合$S$上的非平凡轨道只有一个$\{ a_1, a_2, \cdots, a_r \}$，我们就说$\sigma$是循环（cycle），该非平凡轨道的长度就称为$\sigma$长度。记号$(a_1 a_2 \cdots a_r)$表示该循环$\sigma$作用的链 $$a_1 \mapsto a_2 \mapsto \cdots \mapsto a_r \mapsto a_1.$$ 显然$(a_1 a_2 \cdots a_r) = (a_2 \cdots a_r a_1).$

循环$(a_i)$是平凡的，长度为1，常常省略。两个循环称为是不交的如果它们的非平凡轨道是不交的。

可以证明，任意$\sigma \in S_n$都可以写为不交的非平凡循环的乘积。例如，上述例子$\sigma' = (132)(45)$，平凡循环$(6)$被省略了。这种写法不是唯一的，例如$(321)(45), (54)(123)$都和$\sigma'$一样。

型

首先我们定义一个正整数$n$的分划为非增正整数列$[n_1, n_2, \cdots, n_r]$且满足$\sum_{k=1}^r = n_k.$例如$n = 6$的分划可以是$[2,2,1,1]$等。

定义$\sigma \in S_n$的型（type）是由轨道的元素个数确定的$\sigma$的$n$的分划。例如，上面的$\sigma'$的型为$[3,2,1].$引入型的概念是为了方便描述一个元素$\sigma \in S_n$的所有共轭元。

共轭类

设$(a_1 a_2 \cdots a_r)$是$S_n$中的一个循环，那么$\tau \in S_n$确定的该循环的共轭元为 $$\tau (a_1 a_2 \cdots a_r) \tau^{-1} = (a_1 \tau^{-1}, a_2 \tau^{-1}, \cdots, a_r \tau^{-1}).$$ 这里$a_1 \tau^{-1}$是指$\tau^{-1}$作用在$a_1$上。

两个元素$\sigma_1, \sigma_2$互为共轭元（即存在$\tau \in S_n, \tau \sigma_1 \tau^{-1} = \sigma_2$）当且仅当这两个元素具有相同的型。且$\tau$的确定方式由上一段的定理决定，例如$\sigma' = (132)(45), \sigma'' = (143)(62)$具有相同的型，它们互为共轭元，且使得$\tau \sigma_1 \tau^{-1} = \sigma_2$的$\tau$满足 $$\tau (132)(45) \tau^{-1} = (1\tau^{-1}, 3\tau^{-1}, 2\tau^{-1})(4\tau^{-1},5\tau^{-1}) = (143)(62)$$ 即$$\tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 5 & 2 & 3 & 6 & 4 \end{pmatrix}$$ $S_n$共轭类（一个共轭类就是彼此共轭的元素的集合）的数量就是$n$的分划的方法数。一个共轭类中元素彼此共轭且具有相同的阶。

而一个共轭类中元素的数量就是相同型的元素的排列方式的数量，当然要除去那些排列不同但指同一个元素的情形。例如，$S_6$中型为$[3,2,1]$的所有组合方式有$\binom{6}{3}\binom{3}{2} = 60$种，两个元素组合的循环有一种而三个元素组合的循环有两种，因此实际的共轭类中元素的数量为120个，由此可以推出其他的共轭类的代表元以及元素数量，$S_6$中共轭类为11个，分别是 $$\{ ()^G, (5,6)^G, (4,5,6)^G, (3,4)(5,6)^G, (3,4,5,6)^G, (2,3)(4,5,6)^G, (2,3,4,5,6)^G, (1,2)(3,4)(5,6)^G, (1,2)(3,4,5,6)^G, (1,2,3)(4,5,6)^G, (1,2,3,4,5,6)^G \}$$ 而它们对应的元素数量为$$1 + 15 + 40 + 45 + 90 + 120 + 144 + 15 + 90 + 40 + 120 = 720.$$

以下一个 GAP 代码段可以帮助我们找到2-10阶对称群的元素按共轭类的分解数量，关于此问题的再讨论，详见这里。

A := [];;
for idx in [2..10] do
    Append(A, [(1,idx)]);
    grp := Group(A);
    ccl := ConjugacyClasses(grp);
    s := Size(ccl);
    u := [];
    for jdx in [1..s] do                                       
        Append(u, [Size(ccl[jdx])]);
    od;
    Display(u);
od;

参考资料

1. Paolo Aluffi, Algebra: Chapter 0, GTM Vol.104, American Mathematical Society, 2009-08, ISBN 978-1-4704-6571-1.