离散数学-函数

复合运算可能出现左复合或右复合，因教材而异。一般情况下（由于历史原因），关系的复合运算是右复合-从左向右算，函数的复合运算是左复合-从右向左算。

!!!(2025/4/13)
这个地方老出错的原因是对循环和置换的混淆，循环和置换使用相同的表示方法，在做循环乘时，一定要先区分拿到的是循环还是置换。
在数学中，置换（Permutation）和循环（Cycle）是描述集合元素重新排列的两种方式。它们在组合数学和群论中非常重要。下面分别解释这两种表示方法：

置换（Permutation）

置换是集合中元素的重新排列。对于有限集合，置换可以表示为一个序列，其中每个元素都恰好出现一次。例如，对于集合 ({1, 2, 3, 4, 5, 6})，置换 ((4 1 5 3 6 2)) 表示：

• (1) 被映射到 (4)
• (2) 被映射到 (1)
• (3) 被映射到 (5)
• (4) 被映射到 (3)
• (5) 被映射到 (6)
• (6) 被映射到 (2)

循环（Cycle）

循环是置换的一种特殊表示方式，它将置换表示为一系列循环的乘积。每个循环表示一个元素序列，其中每个元素被映射到序列中的下一个元素，最后一个元素被映射回第一个元素。例如，置换 ((4 1 5 3 6 2)) 可以表示为三个循环的乘积：

• ((1 4 3 5)) 表示 (1 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 1)
• ((2 6)) 表示 (2 \rightarrow 6 \rightarrow 2)

因此，置换 ((4 1 5 3 6 2)) 可以写作 ((1 4 3 5)(2 6))。

表示置换和循环的关系

• 置换可以分解为一系列不相交的循环的乘积。
• 每个循环中的元素都是相互关联的，而不同循环中的元素之间没有直接的映射关系。

在实际应用中，循环表示法通常更简洁，因为它直接反映了置换的结构。例如，置换 ((4 1 5 3 6 2)) 的循环表示法 ((1 4 3 5)(2 6)) 更直观地展示了元素之间的映射关系。

另外，注意，我们学的置换群，主题是针对集合的，表示一个集合中元素的所有置换的集合。

注意以下计算方法是右复合运算的循环乘。

计算循环的乘积

• 找出所有发生改变的位置
• 对每个位置，从第一个轮换开始，到最后一个轮换结束，跟踪变化，记录最终位置
• 将起始位置和最终位置变成置换表达式

eg: (1 4 2 3)· (1 4 3 2) ·(1 2 3)·(1 3 2)= (1 3 4)

首先看位置1

(1 4 2 3) 位置1移动到了位置4

(1 4 3 2) 位置4移动到了位置3

(1 2 3)位置3移动到了位置1

(1 3 2)位置1移动到了位置3

所以最终位置1移动到了位置3

再看位置2

(1 4 2 3) 位置2移动到了位置3

(1 4 3 2) 位置3移动到了位置2

(1 2 3)位置2移动到了位置3

(1 3 2)位置3移动到了位置2

所以最终位置2不改变

再看位置3

(1 4 2 3) 位置3移动到了位置1

(1 4 3 2) 位置1移动到了位置4

(1 2 3)和(1 3 2)不影响位置4

所以最终位置3移动到了位置4

再看位置4

(1 4 2 3) 位置4移动到了位置2

(1 4 3 2) 位置2移动到了位置1

(1 2 3)位置1移动到了位置2

(1 3 2)位置2移动到了位置1

所以最终结果是：

位置1移动到了位置3

位置2不改变

位置3移动到了位置4

位置4移动到了位置1

那么最终化简之后，就是(1 3 4)

证明(证明欧拉函数的乘性)