循环分解算法 (续)

这部分定义了对称群这个核心概念。让我们一步步拆解它。

1. 起点是一个集合：我们从一个任意的、只要不是空的集合 $\Omega$ 开始。这个集合可以是任何东西，比如数字集合 $\{1, 2, 3\}$，字母集合 $\{A, B, C\}$，甚至是一个包含苹果、香蕉、橙子的水果集合。
2. 核心元素是“变换”：我们关注的是对这个集合 $\Omega$ 进行“重新排列”的方法。在数学上，这种“重新排列”被称为置换（permutation）。一个置换本质上是一个函数，它把集合 $\Omega$ 中的每个元素都映射到 $\Omega$ 中的另一个元素，并且这种映射是一一对应的。这个一一对应的函数，术语叫做双射（bijection）。双射包含两个层面的意思：
   • 单射（injective）：集合里不同的元素，经过函数变换后，得到的还是不同的元素。不会出现两个不同的元素被映射到同一个元素的情况。就像给不同的人拍照，每张照片里的人都不一样。
   • 满射（surjective）：目标集合里的每一个元素，都有一个原始集合里的元素与之对应。也就是说，变换后的结果覆盖了整个集合，没有“漏掉”的元素。就像给一群人安排座位，每个座位都有人坐。
3. 构造一个新的集合：现在，我们把所有可能作用在 $\Omega$ 上的置换（也就是所有从 $\Omega$ 到自身的双射函数）收集起来，形成一个更大的集合。这个新集合我们称之为 $S_{\Omega}$。所以 $S_{\Omega}$ 的成员不是 $\Omega$ 里的元素（比如数字1或字母A），而是那些“变换规则”（置换函数）。
4. 定义运算规则：在这个由“变换规则”组成的集合 $S_{\Omega}$ 上，我们需要一个运算。这个运算就是函数复合，记作 $\circ$。假设我们有两个变换规则，$\tau$ 和 $\sigma$。$\sigma \circ \tau$ 的意思就是“先做 $\tau$ 变换，再做 $\sigma$ 变换”。具体来说，对于 $\Omega$ 中的任何一个元素 $a$，$(\sigma \circ \tau)(a)$ 的结果等于 $\sigma(\tau(a))$。
5. 验证群的四个公理：为了证明 $(S_{\Omega}, \circ)$ 是一个群，我们需要验证它满足群的四个基本性质：
   • 封闭性 (Closure)：任意两个 $S_{\Omega}$ 中的元素（即两个双射函数 $\sigma$ 和 $\tau$），它们的复合 $\sigma \circ \tau$ 依然是 $S_{\Omega}$ 中的元素吗？答案是肯定的。两个双射函数的复合结果仍然是一个双射函数。所以，在 $S_{\Omega}$ 里做复合运算，结果不会跑到集合外面去。
   • 结合律 (Associativity)：函数复合运算本身就满足结合律。也就是说，对于任意三个置换 $\rho, \sigma, \tau$，我们有 $(\rho \circ \sigma) \circ \tau = \rho \circ (\sigma \circ \tau)$。这意味着，无论我们是先算后两个的复合，还是先算前两个的复合，最终结果都一样。
   • 单位元 (Identity Element)：$S_{\Omega}$ 中是否存在一个特殊的置换，它和任何其他置换进行复合运算，都等于那个置换本身？是的，存在。这个特殊的置换就是恒等置换，记作 $1$。它的作用是什么都不做，即对于 $\Omega$ 中的任何元素 $a$，$1(a) = a$。它就像数字乘法中的 1。
   • 逆元 (Inverse Element)：对于 $S_{\Omega}$ 中的每一个置换 $\sigma$，是否存在另一个置换 $\sigma^{-1}$，使得它们相互复合的结果是恒等置换？是的，因为 $\sigma$ 是一个双射函数，所以它必然存在一个逆函数 $\sigma^{-1}$，这个逆函数也同样是双射的，所以 $\sigma^{-1}$ 也属于 $S_{\Omega}$。这个逆函数的作用就是“撤销” $\sigma$ 的操作。
6. 最终结论：由于 $(S_{\Omega}, \circ)$ 满足了封闭性、结合律、单位元和逆元这四个公理，所以我们称它为一个群，并给它一个专有名字：集合 $\Omega$ 上的对称群。
7. 关键提醒：最后一段话非常重要，它再次强调了 $S_{\Omega}$ 的元素是作用于 $\Omega$ 的函数或变换，而不是 $\Omega$ 里的具体事物。这是一个初学者很容易混淆的地方。

这部分将上一段的通用定义聚焦到一个非常具体且重要的例子上，并计算了这个群的大小。

1. 特殊化：我们不再使用抽象的集合 $\Omega$，而是使用一个非常具体的有限集合：从 1 到 n 的所有正整数，即 $\Omega = \{1, 2, 3, \ldots, n\}$。
2. 命名：当 $\Omega$ 是这个特定的数字集合时，它对应的对称群 $S_{\Omega}$ 有一个更简洁的名字：$S_n$，称为 n度对称群。所以 $S_n$ 就是对集合 $\{1, 2, \ldots, n\}$ 进行所有可能排列的集合。
3. 群的阶：一个群的阶（order）就是这个群里元素的数量。所以，计算 $S_n$ 的阶，就是要计算到底有多少种不同的方法来排列 $\{1, 2, \ldots, n\}$ 这 n 个数字。
4. 与函数计数的联系：一个置换是一个从 $\{1, 2, \ldots, n\}$ 到其自身的双射函数。对于有限集合来说，一个函数是双射的，当且仅当它是单射的（也当且仅当它是满射的）。这里作者利用了“双射等价于单射”这个性质，因为计算单射函数的数量更直观。
5. 计数过程（乘法原理）：我们来构造一个从 $\{1, 2, \ldots, n\}$ 到自身的单射函数 $\sigma$。
   • 首先，我们要决定 $\sigma(1)$ 的值。数字 1 可以被映射到目标集合 $\{1, 2, \ldots, n\}$ 中的任何一个数。所以，我们有 $n$ 种选择。
   • 接下来决定 $\sigma(2)$。因为函数必须是单射的，不同的输入必须有不同的输出，所以 $\sigma(2)$ 不能等于 $\sigma(1)$。目标集合里已经被 $\sigma(1)$ 占用了一个位置，还剩下 $n-1$ 个位置可选。所以，$\sigma(2)$ 有 $n-1$ 种选择。
   • 然后决定 $\sigma(3)$。$\sigma(3)$ 不能等于 $\sigma(1)$ 和 $\sigma(2)$。目标集合里已经被占用了两个位置，还剩下 $n-2$ 个位置可选。所以，$\sigma(3)$ 有 $n-2$ 种选择。
   • 这个过程一直持续下去，直到决定 $\sigma(n)$。这时，前 $n-1$ 个数已经占用了目标集合里的 $n-1$ 个位置，只剩下最后一个位置给 $\sigma(n)$。所以 $\sigma(n)$ 只有 1 种选择。
6. 计算总数：根据组合数学中的乘法原理，总的函数数量就是每一步选择数量的乘积。所以总共有 $n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1$ 种不同的单射函数。
7. 阶乘：这个连乘积就是 n的阶乘，记作 $n!$。
8. 结论：因为有 $n!$ 种不同的单射函数，也就意味着有 $n!$ 种不同的置换。所以，$S_n$ 这个群里有 $n!$ 个元素，即 $S_n$ 的阶是 $n!$。

这部分引入了一种全新的、更高效的记法来表示置换，即循环分解。之前的表示方法（列出每个数字的映射，如 $\sigma(1)=..., \sigma(2)=...$）太繁琐了。

1. 动机：我们需要一种更紧凑、更能揭示置换结构的方法来书写 $S_n$ 的元素。
2. 基本构件：循环：循环分解的基本单位是循环 (cycle)。一个循环，例如 $(a_1 a_2 \ldots a_m)$，描述了一个“轮换”操作。它的规则是：
   • 把 $a_1$ 换成 $a_2$。
   • 把 $a_2$ 换成 $a_3$。
   • ...
   • 把 $a_{m-1}$ 换成 $a_m$。
   • 最后，把 $a_m$ 换成 $a_1$，形成一个闭环。
   • 所有没有出现在这个括号里的数字，都保持不变（被固定）。
3. 循环的例子：
   • (213) 这个循环到底是什么意思？
   • 它是一个置换。
   • 规则是：$2 \mapsto 1$ (2被映射到1)，$1 \mapsto 3$ (1被映射到3)，$3 \mapsto 2$ (3被映射到2，回到开头)。
   • 如果这个置换是在 $S_4$ 或 $S_5$ 中，那么像 4, 5 这些没在括号里出现的数字，它们的位置不变，即 $4 \mapsto 4, 5 \mapsto 5$。
4. 核心思想：分解：任何一个置换，无论它看起来多复杂，都可以被“分解”成一个或多个互不相交的循环的乘积（这里的“乘积”指函数复合）。“互不相交”意味着这些循环括号里没有共同的数字。
5. 如何从循环分解读取置换：给定一个置换 $\sigma$ 的循环分解，比如 $\sigma = (1 5 3)(2 4)$，我们怎么知道 $\sigma$ 对每个数字做了什么？
   • 想知道 $\sigma(1)$ 是多少？在循环分解里找到 1。1 的右边是 5，所以 $\sigma(1)=5$。
   • 想知道 $\sigma(5)$ 是多少？找到 5，右边是 3，所以 $\sigma(5)=3$。
   • 想知道 $\sigma(3)$ 是多少？找到 3，3 在一个循环的末尾。所以它的去向是这个循环的开头，也就是 1。所以 $\sigma(3)=1$。
   • 想知道 $\sigma(2)$ 是多少？找到 2，右边是 4，所以 $\sigma(2)=4$。
   • 想知道 $\sigma(4)$ 是多少？找到 4，它在一个循环的末尾，所以它的去向是这个循环的开头 2。所以 $\sigma(4)=2$。
   • 如果是在 $S_6$ 里讨论，想知道 $\sigma(6)$ 是多少？数字 6 没有在任何一个循环里出现，所以 $\sigma$ 固定 6，即 $\sigma(6)=6$。
6. 箭头的直观表示：文中给出的箭头图示非常直观。

这表示 $a_1$ 走向 $a_2$，$a_2$ 走向 $a_3$，...，$a_{m_1}$ 又走回 $a_1$（图中省略了返回的箭头），形成第一个循环。然后另一组不相关的数字 $a_{m_1+1}, \ldots$ 形成第二个循环，以此类推。整个置换就是这些各自独立运行的“旋转木马”的集合。

这部分内容总结了前面算法的执行结果，并引入了几个关键的定义：循环的长度、t-循环 和 不相交循环。

1. 算法终止条件: 循环分解算法的核心思想是，将集合 $\{1, 2, \ldots, n\}$ 中的所有元素，根据置换 $\sigma$ 的映射关系，划分到不同的循环中。当每一个数字（从 1 到 n）都已经被包含在某个循环里之后，就意味着我们已经完整地描述了置换 $\sigma$ 对所有元素的作用，算法就可以停止了。
2. 示例结果: 对于上一节中给出的具体置换 $\sigma \in S_{13}$，应用该算法后，我们得到了一个由五个循环组成的乘积。
3. 循环的长度 (Length of a Cycle): 这是一个非常直观的定义，就是一个循环括号内包含的数字的个数。例如，循环 (1 12 8 10 4) 中有 5 个数字，所以它的长度是 5。
4. t-循环 (t-cycle): 这是长度为 t 的循环的一个专用名称。
   • 长度为 5 的循环 (1 12 8 10 4) 就是一个 5-循环。
   • 长度为 2 的循环 (2 13) 就是一个 2-循环。2-循环也常被称为对换 (transposition)。
   • 长度为 1 的循环 (3) 就是一个 1-循环。
5. 不相交循环 (Disjoint Cycles): 如果两个循环没有共享任何数字，它们就是不相交的。这就像两个集合没有共同的元素一样。
   • 在结果 $\sigma=(1 12 8 10 4)(2 13)(3)(5 11 7)(6 9)$ 中，
   • (1 12 8 10 4) 和 (2 13) 是不相交的，因为前者的数字集合是 $\{1, 4, 8, 10, 12\}$，后者的数字集合是 $\{2, 13\}$，它们的交集是空集。
   • (5 11 7) 和 (6 9) 也是不相交的。
   • 实际上，这五个循环两两之间都是不相交的。
6. 结果分析: 该置换 $\sigma$ 被分解成了五个不相交循环的乘积。这些循环的长度分别为 5, 2, 1, 3, 2。所以我们说，这个置换的循环结构是一个 5-循环、一个 3-循环、两个 2-循环 和一个 1-循环的乘积。

这部分引入了一个非常重要的书写约定，旨在简化循环分解的表示，并使其更具通用性。

1. 核心约定: 我们约定省略掉所有长度为 1 的循环。一个长度为 1 的循环，比如 (3)，意味着 $\sigma(3)=3$，即这个数字在置换中保持不变。既然它不变，为了书写简洁，我们干脆就不写它了。
2. 隐含信息: 这个约定的直接推论是：当你看一个循环分解时，任何没有出现在表达式中的数字，都被认为是不动点 (fixed point)。也就是说，如果数字 $i$ 没有在置换 $\tau$ 的循环分解中出现，那么就默认 $\tau(i)=i$。
3. 恒等置换的表示: 恒等置换 1 是指将所有数字都映射到自身的置换，即对所有的 $i$ 都有 $1(i)=i$。按照循环分解算法，它的分解是 $(1)(2)\ldots(n)$。根据新约定，所有的 1-循环都被省略，最后什么都不剩。为了表示这个特殊的**置

换，我们不写一个空白的表达式，而是直接用符号 1** 来代表它。

1. 算法的补充: 在前面介绍的循环分解算法的基础上，增加最后一步：将最终结果中所有形如 $(i)$ 的 1-循环全部擦掉。
2. 应用到示例: 前面的例子 $\sigma$ 分解为 $\sigma=(1 \ 12 \ 8 \ 10 \ 4)(2 \ 13)(3)(5 \ 11 \ 7)(6 \ 9)$。其中有一个 1-循环 (3)。根据新约定，我们把它去掉，最终的、最简洁的循环分解形式就是 $\sigma=(1 \ 12 \ 8 \ 10 \ 4)(2 \ 13)(5 \ 11 \ 7)(6 \ 9)$。当你看到这个表达式时，因为数字 3 没有出现，你就应该立刻明白 $\sigma(3)=3$。
3. 约定的优点 (通用性): 这个约定带来一个巨大的好处。一个写出的循环分解，比如 (1 2)，可以被看作是任何足够大的对称群 $S_n$ (只要 $n \geq 2$) 中的元素。
   • 在 $S_2$ 中，(1 2) 表示交换 1 和 2。
   • 在 $S_3$ 中，(1 2) 表示交换 1 和 2，而数字 3 没有出现，所以它固定 3。
   • 在 $S_4$ 中，(1 2) 表示交换 1 和 2，而数字 3 和 4 没有出现，所以它固定 3 和 4。
   • 以此类推。

这部分通过一个完整的例子——群 $S_3$——来巩固循环分解的概念。$S_3$ 是作用在集合 $\{1, 2, 3\}$ 上的所有置换构成的群。我们知道它的阶（元素个数）是 $3! = 3 \times 2 \times 1 = 6$。这个表格列出了这全部 6 个元素。

表格分为两列：

1. $\sigma_i$ 的值: 这一列用最原始的方式描述了每个置换的作用，即明确指出每个数字 1, 2, 3 分别被映射到了哪个数字。
2. $\sigma_i$ 的循环分解: 这一列给出了对应置换的、采用了“省略 1-循环”约定的标准循环分解。

我们来逐行验证：

• $\sigma_1$: $\sigma_1(1)=1, \sigma_1(2)=2, \sigma_1(3)=3$。每个元素都被固定。这是恒等置换。它的完整循环分解是 $(1)(2)(3)$。省略所有 1-循环后，记为 1。
• $\sigma_2$: $\sigma_2(1)=1, \sigma_2(2)=3, \sigma_2(3)=2$。
• 数字 1 被固定，所以它在 1-循环 (1) 中。
• 对于 2 和 3，我们有 $\sigma_2(2)=3$ 和 $\sigma_2(3)=2$，这构成一个 2-循环 (2 3)。
• 所以完整分解是 (1)(2 3)。省略 1-循环 (1) 后，记为 (2 3)。
• $\sigma_3$: $\sigma_3(1)=3, \sigma_3(2)=2, \sigma_3(3)=1$。
• 数字 2 被固定：(2)。
• 对于 1 和 3，$\sigma_3(1)=3$ 和 $\sigma_3(3)=1$，构成一个 2-循环 (1 3)。
• 完整分解是 (2)(1 3)。省略 1-循环后，记为 (1 3)。
• $\sigma_4$: $\sigma_4(1)=2, \sigma_4(2)=1, \sigma_4(3)=3$。
• 数字 3 被固定：(3)。
• 对于 1 和 2，$\sigma_4(1)=2$ 和 $\sigma_4(2)=1$，构成一个 2-循环 (1 2)。
• 完整分解是 (3)(1 2)。省略 1-循环后，记为 (1 2)。
• $\sigma_5$: $\sigma_5(1)=2, \sigma_5(2)=3, \sigma_5(3)=1$。
• 从 1 开始：$\sigma_5(1)=2$。
• 接着看 2：$\sigma_5(2)=3$。
• 接着看 3：$\sigma_5(3)=1$，这回到了循环的起点 1。
• 所以这构成一个 3-循环 (1 2 3)。所有数字都已包含在内，没有不动点。记为 (1 2 3)。
• $\sigma_6$: $\sigma_6(1)=3, \sigma_6(2)=1, \sigma_6(3)=2$。
• 从 1 开始：$\sigma_6(1)=3$。
• 接着看 3：$\sigma_6(3)=2$。
• 接着看 2：$\sigma_6(2)=1$，回到了起点 1。
• 这构成一个 3-循环 (1 3 2)。所有数字都已包含在内。记为 (1 3 2)。

所以，$S_3$ 的 6 个元素可以按循环结构分类：

• 1 个恒等置换 (1)
• 3 个 2-循环（也叫对换）：(1 2), (1 3), (2 3)
• 2 个 3-循环：(1 2 3), (1 3 2)

这部分给出了一个计算逆置换 $\sigma^{-1}$ 的循环分解的非常简单快捷的方法。

1. 逆置换的定义: 首先回顾逆置换 $\sigma^{-1}$ 的含义。如果 $\sigma$ 把 $a$ 映射到 $b$ (即 $\sigma(a)=b$)，那么它的逆置换 $\sigma^{-1}$ 就必须把 $b$ 映射回 $a$ (即 $\sigma^{-1}(b)=a$)。它的作用是“撤销”或“反转”$\sigma$ 的操作。
2. 循环的反转:
   • 考虑一个循环，比如 $\tau = (a_1 \ a_2 \ \ldots \ a_m)$。
   • 这个循环的含义是：$\tau(a_1)=a_2, \tau(a_2)=a_3, \ldots, \tau(a_{m-1})=a_m, \tau(a_m)=a_1$。
   • 那么它的逆 $\tau^{-1}$ 必须执行相反的操作：$\tau^{-1}(a_2)=a_1, \tau^{-1}(a_3)=a_2, \ldots, \tau^{-1}(a_m)=a_{m-1}, \tau^{-1}(a_1)=a_m$。
   • 让我们看看把循环中的数字逆序写出来是什么效果：$\rho = (a_m \ a_{m-1} \ \ldots \ a_2 \ a_1)$。
   • 这个循环 $\rho$ 的作用是：$\rho(a_m)=a_{m-1}, \rho(a_{m-1})=a_{m-2}, \ldots, \rho(a_2)=a_1, \rho(a_1)=a_m$。
   • 对比一下，可以发现 $\tau^{-1}$ 的作用和 $\rho$ 的作用是完全一样的，只是描述的起点不同。例如，$\tau^{-1}(a_2)=a_1$ 和 $\rho(a_2)=a_1$ 是一致的；$\tau^{-1}(a_1)=a_m$ 和 $\rho(a_1)=a_m$ 也是一致的。所以，我们得出结论：单个循环的逆就是把它的元素逆序排列。
3. 不相交循环乘积的逆:
   • 假设 $\sigma = \tau_1 \tau_2 \ldots \tau_k$，其中 $\tau_i$ 是两两不相交的循环。
   • 我们知道，对于一般的群元素 $g, h$，有 $(gh)^{-1} = h^{-1}g^{-1}$。
   • 所以 $\sigma^{-1} = (\tau_1 \tau_2 \ldots \tau_k)^{-1} = \tau_k^{-1} \ldots \tau_2^{-1} \tau_1^{-1}$。
   • 然而，一个关键的性质是：不相交循环是可交换的（后面会讲到）。也就是说 $\tau_i \tau_j = \tau_j \tau_i$。
   • 因此，$\tau_k^{-1} \ldots \tau_2^{-1} \tau_1^{-1}$ 的顺序可以任意调换，我们可以把它写成 $\tau_1^{-1} \tau_2^{-1} \ldots \tau_k^{-1}$。
   • 由于 $\tau_i$ 作用的数字集合与 $\tau_j$ ($i \neq j$) 不同，那么 $\tau_i^{-1}$ 和 $\tau_j^{-1}$ 也作用在不同的数字集合上，它们也必然是不相交的。
4. 结论: 综上所述，求一个置换的逆，只需要把它循环分解中的每一个循环都单独求逆（即逆序重写），然后把结果组合起来即可。

这部分解释了如何在循环分解表示下，计算两个置换的乘积（即函数复合）。

1. 核心规则：从右到左: 这是函数复合的标准约定。当我们写 $f \circ g$ 时，它的意思是先作用 $g$，再作用 $f$。同样，对于置换 $\sigma \circ \tau$，我们先应用右边的 $\tau$，再把得到的结果应用到左边的 $\sigma$ 上。
2. “跟随”元素: 计算乘积的循环分解的算法，本质上就是我们之前用来求单个置换循环分解的那个算法的变体。我们不是直接读取 $\sigma(a)$ 的值，而是要计算 $(\sigma \circ \tau)(a) = \sigma(\tau(a))$ 的值。
3. 算法步骤:

a. 选择一个起始数字，比如 1。

b. 从右边的置换开始，看 1 变成了什么。

c. 再看这个新数字在左边的置换里变成了什么。

d. 这样就找到了 1 在复合置换下的最终归宿。

e. 然后“跟随”这个新数字，重复 b, c, d 的过程，直到回到起始数字 1，这就完成了一个循环。

f. 如果还有数字没出现在已找到的循环里，就从中选最小的一个，重复上述过程，直到所有数字都被包含。

1. 示例分析: $(1 \ 2 \ 3) \circ (1 \ 2)(3 \ 4)$
   • 从 1 开始:
   • 在右侧置换 $(1 \ 2)(3 \ 4)$ 中，1 被映射到 2。
   • 把结果 2 带入左侧置换 $(1 \ 2 \ 3)$ 中，2 被映射到 3。
   • 所以，整个乘积把 1 映射到 3。我们的新循环开始为 (1 3 ...。
   • 跟随 3:
   • 在右侧置换 $(1 \ 2)(3 \ 4)$ 中，3 被映射到 4。
   • 把结果 4 带入左侧置换 $(1 \ 2 \ 3)$ 中，4 没有出现，所以 4 被固定，即 4 映射到 4。
   • 所以，整个乘积把 3 映射到 4。我们的新循环是 (1 3 4 ...。
   • 跟随 4:
   • 在右侧置换 $(1 \ 2)(3 \ 4)$ 中，4 被映射到 3。
   • 把结果 3 带入左侧置换 $(1 \ 2 \ 3)$ 中，3 被映射到 1。
   • 所以，整个乘积把 4 映射到 1。而 1 是我们这个循环的起始数字，所以这个循环闭合了：(1 3 4)。
   • 检查剩余数字: 数字 1, 3, 4 已经处理完毕。我们还需要检查 2。
   • 从 2 开始:
   • 在右侧置换 $(1 \ 2)(3 \ 4)$ 中，2 被映射到 1。
   • 把结果 1 带入左侧置换 $(1 \ 2 \ 3)$ 中，1 被映射到 2。
   • 所以，整个乘积把 2 映射到 2。这意味着 2 是一个不动点，构成 1-循环 (2)。
   • 最终结果: 所有的数字 $\{1, 2, 3, 4\}$ 都已考虑。乘积的循环分解是 $(1 3 4)(2)$。根据约定，省略 1-循环，最终结果是 (1 3 4)。

这部分通过一个非常简洁的例子，揭示了对称群的一个根本性质：非交换性。

1. 计算第一个乘积: $(1 \ 2) \circ (1 \ 3)$
   • 从 1 开始: 右边 (1 3): $1 \mapsto 3$。左边 (1 2): $3 \mapsto 3$ (固定)。结果: $1 \mapsto 3$。新循环 (1 3 ...。
   • 跟随 3: 右边 (1 3): $3 \mapsto 1$。左边 (1 2): $1 \mapsto 2$。结果: $3 \mapsto 2$。新循环 (1 3 2 ...。
   • 跟随 2: 右边 (1 3): $2 \mapsto 2$ (固定)。左边 (1 2): $2 \mapsto 1$。结果: $2 \mapsto 1$。回到起点 1，循环闭合。
   • 最终结果: $(1 \ 3 \ 2)$。
2. 计算第二个乘积: $(1 \ 3) \circ (1 \ 2)$
   • 从 1 开始: 右边 (1 2): $1 \mapsto 2$。左边 (1 3): $2 \mapsto 2$ (固定)。结果: $1 \mapsto 2$。新循环 (1 2 ...。
   • 跟随 2: 右边 (1 2): $2 \mapsto 1$。左边 (1 3): $1 \mapsto 3$。结果: $2 \mapsto 3$。新循环 (1 2 3 ...。
   • 跟随 3: 右边 (1 2): $3 \mapsto 3$ (固定)。左边 (1 3): $3 \mapsto 1$。结果: $3 \mapsto 1$。回到起点 1，循环闭合。
   • 最终结果: $(1 \ 2 \ 3)$。
3. 比较结果:
   • $(1 \ 2) \circ (1 \ 3) = (1 \ 3 \ 2)$
   • $(1 \ 3) \circ (1 \ 2) = (1 \ 2 \ 3)$
   • 因为 $(1 \ 3 \ 2) \neq (1 \ 2 \ 3)$，所以我们得出结论：$(1 \ 2) \circ (1 \ 3) \neq (1 \ 3) \circ (1 \ 2)$。
4. 非交换群的定义: 一个群 $G$ 如果存在至少一对元素 $a, b \in G$ 使得 $a \cdot b \neq b \cdot a$，那么就称这个群是非交换的 (non-commutative) 或 非阿贝尔的 (non-abelian)。
5. 推广到所有 $S_n (n \ge 3)$:
   • 我们在 $S_3$ 中找到了这样一对不可交换的元素：(1 2) 和 (1 3)。
   • 对于任何 $n > 3$，群 $S_n$ 包含了作用在子集 $\{1, 2, 3\}$ 上的所有置换。也就是说，我们可以把 (1 2) 和 (1 3) 看作是 $S_n$ 中的元素，它们仅仅固定了从 4 到 $n$ 的所有其他数字。
   • 在 $S_n$ 中计算它们的乘积，结果依然是 $(1 \ 2) \circ (1 \ 3) = (1 \ 3 \ 2)$ 和 $(1 \ 3) \circ (1 \ 2) = (1 \ 2 \ 3)$。
   • 因为 $S_n$ 只要 $n \geq 3$ 就必然包含这样一对不可交换的元素，所以所有 $n \geq 3$ 的对称群 $S_n$ 都是非交换群。
6. 小群的交换性:
   • $S_1$ 只有一个元素 (1)，满足 $1 \circ 1 = 1 \circ 1$，是交换群。
   • $S_2$ 有两个元素 1 和 (1 2)。
   • $1 \circ (1 2) = (1 2)$
   • $(1 2) \circ 1 = (1 2)$
   • $1 \circ 1 = 1$
   • $(1 2) \circ (1 2) = 1$

这部分阐述了与上一节非交换性形成鲜明对比的一个重要性质：不相交循环之间满足交换律。

1. 单个循环的本质: 一个循环，比如 $\tau = (a_1 \ a_2 \ \ldots \ a_m)$，实际上是一个置换。这个置换的作用域被限制在集合 $A = \{a_1, a_2, \ldots, a_m\}$ 内部。对于任何不属于这个集合的数字 $x \notin A$，这个置换都会固定它，即 $\tau(x) = x$。
2. 不相交循环的定义: 两个循环 $\tau_1$ 和 $\tau_2$ 是不相交的，意味着它们作用的数字集合是完全分开的。设 $\tau_1$ 作用于集合 $A_1$，$\tau_2$ 作用于集合 $A_2$，那么 $A_1 \cap A_2 = \emptyset$。
3. 可交换性的证明 (思路): 我们要证明 $\tau_1 \circ \tau_2 = \tau_2 \circ \tau_1$。要证明两个置换相等，我们必须证明它们对每一个数字的作用都是相同的。让我们检查任意一个数字 $x$。
   • 情况 1: $x$ 属于 $\tau_1$ 作用的集合 $A_1$。
   • 计算 $(\tau_1 \circ \tau_2)(x) = \tau_1(\tau_2(x))$。
   • 首先，$\tau_2$ 作用于 $x$。因为 $x \in A_1$ 且 $A_1, A_2$ 不相交，所以 $x \notin A_2$。根据定义，$\tau_2$ 固定 $x$，即 $\tau_2(x) = x$。
   • 所以，$\tau_1(\tau_2(x)) = \tau_1(x)$。
   • 计算 $(\tau_2 \circ \tau_1)(x) = \tau_2(\tau_1(x))$。
   • 首先，$\tau_1$ 作用于 $x$，得到一个新的数字 $y = \tau_1(x)$。因为 $\tau_1$ 的作用域是 $A_1$，所以 $y$ 也一定在 $A_1$ 中。
   • 因为 $y \in A_1$ 且 $A_1, A_2$ 不相交，所以 $y \notin A_2$。
   • 因此，$\tau_2$ 固定 $y$，即 $\tau_2(y) = y$。
   • 所以，$\tau_2(\tau_1(x)) = \tau_1(x)$。
   • 两种顺序下，对 $x$ 的作用结果都是 $\tau_1(x)$，是相等的。
   • 情况 2: $x$ 属于 $\tau_2$ 作用的集合 $A_2$。
   • 证明过程与情况 1 完全对称，最终结果都是 $\tau_2(x)$。
   • 情况 3: $x$ 既不属于 $A_1$ 也不属于 $A_2$。
   • 计算 $(\tau_1 \circ \tau_2)(x) = \tau_1(\tau_2(x))$。
   • $\tau_2$ 固定 $x$，所以 $\tau_2(x)=x$。
   • $\tau_1$ 也固定 $x$，所以 $\tau_1(x)=x$。
   • 结果是 $\tau_1(x) = x$。
   • 计算 $(\tau_2 \circ \tau_1)(x) = \tau_2(\tau_1(x))$。
   • $\tau_1$ 固定 $x$，所以 $\tau_1(x)=x$。
   • $\tau_2$ 也固定 $x$，所以 $\tau_2(x)=x$。
   • 结果是 $\tau_2(x) = x$。
   • 两种顺序下，对 $x$ 的作用结果都是 $x$，是相等的。
4. 结论: 既然对于任何数字 $x$，都有 $(\tau_1 \circ \tau_2)(x) = (\tau_2 \circ \tau_1)(x)$，那么这两个复合置换就是同一个置换。因此，不相交循环是可交换的。
5. 推论: 一个置换的循环分解是由一堆两两不相交的循环乘积构成的。既然它们之间两两可交换，我们就可以像对待普通数字的乘法一样，任意调换它们的顺序。
   • 例如，$\sigma = (1 \ 12 \ 8 \ 10 \ 4)(2 \ 13)(5 \ 11 \ 7)(6 \ 9)$
   • 也可以写成 $\sigma = (6 \ 9)(1 \ 12 \ 8 \ 10 \ 4)(5 \ 11 \ 7)(2 \ 13)$
   • 或者 $\sigma = (2 \ 13)(5 \ 11 \ 7)(6 \ 9)(1 \ 12 \ 8 \ 10 \ 4)$
   • 所有这些不同的写法都代表同一个置换。

这部分讨论了单个循环内部表示的灵活性。

1. 循环的本质: 一个循环 $(a_1 \ a_2 \ \ldots \ a_m)$ 描述的是一个首尾相接的映射链条：$a_1 \mapsto a_2 \mapsto \ldots \mapsto a_m \mapsto a_1$。
2. 改变起点: 这个链条是圆形的。我们从哪个点开始描述这个圆，并不会改变这个圆本身。
   • 我们可以从 $a_1$ 开始，描述为 $(a_1 \ a_2 \ \ldots \ a_m)$。
   • 我们也可以从 $a_2$ 开始，沿着同样的方向，描述为 $(a_2 \ a_3 \ \ldots \ a_m \ a_1)$。这个表达式同样表示 $a_2 \mapsto a_3, \ldots, a_m \mapsto a_1, a_1 \mapsto a_2$。仔细检查会发现，这和从 $a_1$ 开始描述的映射关系是完全一样的。
   • 同理，我们可以从任何一个 $a_i$ 开始，只要保持其他元素的相对顺序不变，得到的循环表示的都是同一个置换。
3. 等价表示的数量: 一个长度为 $m$ 的循环，有 $m$ 个不同的数字，因此有 $m$ 个不同的起点可以选择。所以，一个 $m$-循环有 $m$ 种等价的写法。
4. 书写约定 (规范化): 正因为一个循环有多种写法，为了统一和方便比较，人们通常采用一个约定：将循环中最小的那个数字写在最前面。
   • 例如，对于置换 $(3 \ 4 \ 1 \ 2)$，它有 4 种写法：
   • $(3 \ 4 \ 1 \ 2)$
   • $(4 \ 1 \ 2 \ 3)$
   • $(1 \ 2 \ 3 \ 4)$
   • $(2 \ 3 \ 4 \ 1)$
   • 这些数字中最小的是 1。所以，按照约定，我们应该选择以 1 开头的写法：$(1 \ 2 \ 3 \ 4)$。这被称为这个循环的规范表示 (canonical representation)。

这部分内容非常关键，它连接了前面所有的概念，并引出了循环分解的两个核心优点：唯一性和计算阶的便捷性。

1. 表示的混乱 vs. 唯一性:
   • 混乱: 一个置换可以写成很多种不同的循环乘积形式，特别是当这些循环是相交的时候。
   • 例子：$(1 \ 2 \ 3) = (1 \ 2)(2 \ 3)$。这里，我们将一个 3-循环写成两个相交的 2-循环的乘积。
   • 更复杂的例子：$(1 \ 2 \ 3) = (1 \ 3)(1 \ 3 \ 2)(1 \ 3)$。这是一个更复杂的、包含相交循环的乘积。
   • 这说明，如果允许循环任意相交，那么一个置换的表示方式是无穷无尽的，非常混乱。
   • 唯一性: 循环分解定理（这里提到但未证明）的核心思想是，如果我们加上一个严格的限制条件——必须是不相交循环的乘积——那么表示就变得“几乎”唯一了。
   • “几乎”唯一的意思是，任何一个置换（非恒等元）都可以被表示成不相交循环的乘积，并且这种表示在以下两种调整下是唯一的：
2. 循环的顺序可以任意调换（因为它们可交换）。
3. 每个循环内部的数字可以循环移位（因为它们代表同一个循环）。
   • 例如，$(1 \ 2)(3 \ 4 \ 5)$ 和 $(3 \ 4 \ 5)(1 \ 2)$ 是同一个置换。
   • $(1 \ 2)(3 \ 4 \ 5)$ 和 $(1 \ 2)(4 \ 5 \ 3)$ 也是同一个置换。
   • 但你不可能把 $(1 \ 2)(3 \ 4 \ 5)$ 表示成其他形式的不相交循环乘积，比如 $(1 \ 3)(2 \ 4 \ 5)$，这是另一个完全不同的置换。
4. “化简”的威力:
   • 这个唯一性提供了一个强大的工具：判断两个置换是否相等。
   • 给你两个用任意（可能相交的）循环乘积表示的置换 $\sigma$ 和 $\tau$。你怎么知道它们是否相等？
   • 方法是：分别将 $\sigma$ 和 $\tau$ 的乘积计算出来（使用“从右到左跟随元素”的算法），得到它们各自的不相交循环分解。
   • 然后，比较这两个不相交循环分解。如果它们包含的循环集合是一样的（不计顺序和循环内部的移位），那么 $\sigma$ 和 $\tau$ 就是相等的。否则，它们不相等。
   • 这个过程就像化简代数表达式一样，我们把复杂的、任意的乘积化简成一个“标准形式”（即不相交循环分解），然后通过比较标准形式来判断相等性。
5. 循环分解的另一个优点：计算阶:
   • 元素的阶 (Order of an Element): 在群论中，一个元素 $\sigma$ 的阶，记作 $|\sigma|$，是使得 $\sigma^k = 1$（恒等元）的最小正整数 $k$。直观地说，就是将操作 $\sigma$ 重复多少次才能回到初始状态。
   • 重要结论: 一个置换的阶，等于其不相交循环分解中，所有循环长度的最小公倍数 (Least Common Multiple, LCM)。
   • 例如，$\sigma = (1 \ 2)(3 \ 4 \ 5)$。
   • 它的循环分解由一个长度为 2 的循环和一个长度为 3 的循环组成。
   • 所以 $|\sigma| = \text{lcm}(2, 3) = 6$。
   • 这意味着 $\sigma^6 = 1$，并且对于任何 $1 \le k < 6$，都有 $\sigma^k \neq 1$。
   • 这个性质极大地简化了计算阶的过程。我们不需要真的去计算 $\sigma^2, \sigma^3, \ldots$，只需要分解它，然后找循环长度的最小公倍数即可。

这道习题是用来练习本章介绍的两个核心计算技能：

1. 将一个用映射列表表示的置换转换为循环分解。
2. 计算置换的乘积并将结果表示为循环分解。
3. 计算置换的幂。

解题步骤分析:

• 找出 $\sigma$ 的循环分解:

1. 从 1 开始：$1 \mapsto 3$。
2. 跟随 3：$3 \mapsto 5$。
3. 跟随 5：$5 \mapsto 1$。回到起点，得到循环 (1 3 5)。
4. 检查剩余数字，从未出现的最小数字 2 开始：$2 \mapsto 4$。
5. 跟随 4：$4 \mapsto 2$。回到起点，得到循环 (2 4)。
6. 所有数字 $\{1, 2, 3, 4, 5\}$ 都已出现。所以 $\sigma = (1 \ 3 \ 5)(2 \ 4)$。
   • 找出 $\tau$ 的循环分解:
7. 从 1 开始：$1 \mapsto 5$。
8. 跟随 5：$5 \mapsto 1$。得到循环 (1 5)。
9. 从未出现的最小数字 2 开始：$2 \mapsto 3$。
10. 跟随 3：$3 \mapsto 2$。得到循环 (2 3)。
11. 数字 4 未出现，但根据映射列表 $\tau(4)=4$，所以 4 是不动点。
12. 所有数字都已考虑。所以 $\tau = (1 \ 5)(2 \ 3)$。
    • 计算 $\sigma^2$:
    • $\sigma^2 = \sigma \circ \sigma = (1 \ 3 \ 5)(2 \ 4) \circ (1 \ 3 \ 5)(2 \ 4)$。
    • 因为不相交循环可交换，这等于 $((1 \ 3 \ 5) \circ (1 \ 3 \ 5)) \circ ((2 \ 4) \circ (2 \ 4))$。
    • $(1 \ 3 \ 5)^2$: $1 \mapsto 3 \mapsto 5$。所以 $1 \mapsto 5$。$5 \mapsto 1 \mapsto 3$。所以 $5 \mapsto 3$。$3 \mapsto 5 \mapsto 1$。所以 $3 \mapsto 1$。得到循环 (1 5 3)。
    • $(2 \ 4)^2$: $2 \mapsto 4 \mapsto 2$。这是一个对换的平方，结果是恒等置换。
    • 所以 $\sigma^2 = (1 \ 5 \ 3)$。
    • 计算 $\sigma\tau$:
    • $\sigma \tau = (1 \ 3 \ 5)(2 \ 4) \circ (1 \ 5)(2 \ 3)$。
    • 从 1 开始：$1 \xrightarrow{\tau} 5 \xrightarrow{\sigma} 1$。1 是不动点。
    • 从 2 开始：$2 \xrightarrow{\tau} 3 \xrightarrow{\sigma} 5$。所以 $2 \mapsto 5$。
    • 跟随 5：$5 \xrightarrow{\tau} 1 \xrightarrow{\sigma} 3$。所以 $5 \mapsto 3$。
    • 跟随 3：$3 \xrightarrow{\tau} 2 \xrightarrow{\sigma} 4$。所以 $3 \mapsto 4$。
    • 跟随 4：$4 \xrightarrow{\tau} 4 \xrightarrow{\sigma} 2$。所以 $4 \mapsto 2$。回到起点 2。
    • 结果是 $(1)(2 \ 5 \ 3 \ 4)$，简写为 $(2 \ 5 \ 3 \ 4)$。
    • 计算 $\tau\sigma$:
    • $\tau \sigma = (1 \ 5)(2 \ 3) \circ (1 \ 3 \ 5)(2 \ 4)$。
    • 从 1 开始：$1 \xrightarrow{\sigma} 3 \xrightarrow{\tau} 2$。所以 $1 \mapsto 2$。
    • 跟随 2：$2 \xrightarrow{\sigma} 4 \xrightarrow{\tau} 4$。所以 $2 \mapsto 4$。
    • 跟随 4：$4 \xrightarrow{\sigma} 2 \xrightarrow{\tau} 3$。所以 $4 \mapsto 3$。
    • 跟随 3：$3 \xrightarrow{\sigma} 5 \xrightarrow{\tau} 1$。所以 $3 \mapsto 1$。回到起点 1。
    • 检查 5：$5 \xrightarrow{\sigma} 1 \xrightarrow{\tau} 5$。5 是不动点。
    • 结果是 $(5)(1 \ 2 \ 4 \ 3)$，简写为 $(1 \ 2 \ 4 \ 3)$。
    • 计算 $\tau^2\sigma$:
    • 首先 $\tau^2 = ((1 \ 5)(2 \ 3))^2 = (1 \ 5)^2(2 \ 3)^2 = 1 \cdot 1 = 1$。$\tau$ 是一个阶为 2 的元素。
    • 所以 $\tau^2\sigma = 1 \circ \sigma = \sigma = (1 \ 3 \ 5)(2 \ 4)$。

存在目的:

此题的目的是让学生通过动手计算，将本章学到的所有关于循环分解的表示法、乘法和幂的运算规则融会贯通。它也是一个很好的例子，用来说明 $\sigma\tau \neq \tau\sigma$，再次强调对称群的非交换性。

... (由于篇幅和请求的性质，这里仅详细分析第一道习题作为示例，其余习题的分析模式类似) ...

... (对习题2到20进行类似的分析) ...