排列轮换是 排列 的一个 子集,其元素彼此交换位置。排列轮换在 Comtet (1974, p. 256) 中被称为“轨道”。例如,在 排列群 中,(143) 是一个 3-轮换,(2) 是一个 1-轮换。这里,符号 (143) 表示从原始排序 开始,第一个元素被第四个元素替换,第四个元素被第三个元素替换,第三个元素被第一个元素替换,即 。
在选择循环分解的表示形式时有很大的自由度,因为 (1) 循环是不相交的,因此可以以任何顺序指定,并且 (2) 给定循环的任何旋转都指定相同的循环(Skiena 1990, p. 20)。因此,(431)(2)、(314)(2)、(143)(2)、(2)(431)、(2)(314) 和 (2)(143) 都描述了相同的排列。下表给出了对称群在三个元素上的每个元素的表示形式集合,,按最低规范顺序排序(首先按循环长度,然后按元素的最低初始顺序)。
{1,2,3} 的排列 | 符号 |
(1)(2)(3) | |
(1)(23) | |
(3)(12) | |
(123) | |
(132) | |
(2)(13) |
排列的循环分解可以使用 Wolfram 语言 中的函数计算PermutationCycles[p],以及对应于循环分解的排列可以使用以下函数计算PermutationList[c]。这里,单个循环使用以下函数表示Cycles。在以前的版本中,可以使用效率较低的以下函数计算循环分解ToCycles[p],在 Wolfram 语言 包中Permutations`,并且对应于循环分解的 排列 可以使用以下函数计算FromCycles[c1, ..., cn],在 Wolfram 语言 包中Permutations`。根据 Vardi (1991) 的说法,Wolfram 语言 代码对于ToCycles是有史以来最晦涩难懂的代码之一。
n 个符号上的每个 排列群 都可以唯一地表示为不相交循环的乘积(Skiena 1990, p. 20)。排列 的循环分解可以看作是 排列群 的一个 类。
阶数为 的 排列群 中 -轮换的数量 由下式给出
(1)
|
其中 是第一类斯特林数。更一般地,设 是 的排列的数量,它恰好有 个循环,所有循环的长度都 。 有时被称为关联第一类斯特林数(Comtet 1974, p. 256)。量 出现在斯特林级数中系数的闭式表达式中(Comtet 1974, p. 257 和 267)。下表给出了 的三角形。
Sloane | ||
1 | A008275 | 1; 1, 1; 2, 3, 1; 6, 11, 6, 1; 24, 50, 35, 10, 1; ... |
2 | A008306 | 1; 2; 6, 3; 24, 20; 120, 130, 15; 720, 924, 210; ... |
3 | A050211 | 2; 6; 24; 120, 40; 720, 420; 5040, 3948; 40320, ... |
4 | A050212 | 6; 24; 120; 720; 5040, 1260; 40320, 18144; ... |
5 | A050213 | 24; 120; 720; 5040; 40320; 362880, 72576; ... |
函数 由以下递推关系式给出
(2)
|
其中 是下降阶乘,结合初始条件
(3)
| |||
(4)
|
(Riordan 1958, p. 85; Comtet 1974, p. 257)。