主题
Search

排列轮换


排列轮换是 排列 的一个 子集,其元素彼此交换位置。排列轮换在 Comtet (1974, p. 256) 中被称为“轨道”。例如,在 排列群 {4,2,1,3} 中,(143) 是一个 3-轮换,(2) 是一个 1-轮换。这里,符号 (143) 表示从原始排序 {1,2,3,4} 开始,第一个元素被第四个元素替换,第四个元素被第三个元素替换,第三个元素被第一个元素替换,即 1->4->3->1

在选择循环分解的表示形式时有很大的自由度,因为 (1) 循环是不相交的,因此可以以任何顺序指定,并且 (2) 给定循环的任何旋转都指定相同的循环(Skiena 1990, p. 20)。因此,(431)(2)、(314)(2)、(143)(2)、(2)(431)、(2)(314) 和 (2)(143) 都描述了相同的排列。下表给出了对称群在三个元素上的每个元素的表示形式集合,S_3,按最低规范顺序排序(首先按循环长度,然后按元素的最低初始顺序)。

{1,2,3} 的排列符号
{1,2,3}(1)(2)(3)
{1,3,2}(1)(23)
{2,1,3}(3)(12)
{2,3,1}(123)
{3,1,2}(132)
{3,2,1}(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)。排列 的循环分解可以看作是 排列群 的一个

阶数为 n排列群k-轮换的数量 d_1(n,k) 由下式给出

 d_1(n,k)=(-1)^(n-k)S_1(n,k)=|S_1(n,k)|,
(1)

其中 S_1(n,m)第一类斯特林数。更一般地,设 d_r(n,k)n 的排列的数量,它恰好有 k 个循环,所有循环的长度都 >=rd_2(n,k) 有时被称为关联第一类斯特林数(Comtet 1974, p. 256)。量 d_3(n,k) 出现在斯特林级数中系数的闭式表达式中(Comtet 1974, p. 257 和 267)。下表给出了 d_r(n,k) 的三角形。

rSloaned_r(n,k)
1A0082751; 1, 1; 2, 3, 1; 6, 11, 6, 1; 24, 50, 35, 10, 1; ...
2A0083061; 2; 6, 3; 24, 20; 120, 130, 15; 720, 924, 210; ...
3A0502112; 6; 24; 120, 40; 720, 420; 5040, 3948; 40320, ...
4A0502126; 24; 120; 720; 5040, 1260; 40320, 18144; ...
5A05021324; 120; 720; 5040; 40320; 362880, 72576; ...

函数 d_r(n,k) 由以下递推关系式给出

 d_r(n,k)=(n-1)d_r(n-1,k)+(n-1)_(r-1)d_r(n-r,k-1),
(2)

其中 (n)_k下降阶乘,结合初始条件

d_r(n,k)=0  for n<=kr-1
(3)
d_r(n,1)=(n-1)!
(4)

(Riordan 1958, p. 85; Comtet 1974, p. 257)。


另请参阅

Golomb-Dickman 常数, 排列, 排列群, 第一类斯特林数, 斯特林级数, 子集

使用 Wolfram|Alpha 探索

参考文献

Biggs, N. 离散数学,修订版。 Oxford, England: Clarendon Press, 1993.Comtet, L. 高级组合数学:有限与无限展开的艺术,修订和扩充版。 Dordrecht, Netherlands: Reidel, p. 257, 1974.Graham, R. L.; Knuth, D. E.; and Patashnik, O. 具体数学:计算机科学的基础,第二版。 Reading, MA: Addison-Wesley, 1994.Knuth, D. E. 计算机程序设计艺术,第 1 卷:基本算法,第三版。 Reading, MA: Addison-Wesley, 1997.Riordan, J. 组合恒等式。 New York: Wiley, 1958.Skiena, S. "排列的循环结构。" §1.2.4 in 使用 Mathematica 实现离散数学:组合数学和图论。 Reading, MA: Addison-Wesley, pp. 20-24, 1990.Sloane, N. J. A. Sequences A008275, A008306, A050211, A050212, A050213 in "整数序列在线百科全书。"Stanton, D. and White, D. 构造组合数学。 New York: Springer-Verlag, 1986.Vardi, I. 使用 Mathematica 的计算娱乐。 Redwood City, CA: Addison-Wesley, p. 223, 1991.

在 Wolfram|Alpha 中被引用

排列轮换

引用为

Weisstein, Eric W. "Permutation Cycle." 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/PermutationCycle.html

主题分类