主題
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 常數, 排列, 排列群, 第一類斯特林數, 斯特林級數, 子集

使用 探索

參考文獻

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.

在 中被引用

排列輪換

引用為

Weisstein, Eric W. "Permutation Cycle." 來自 —— 資源。 https://mathworld.tw/PermutationCycle.html

主題分類