主題
Search

排列

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

排列，也稱為“安排數”或“次序”，是有序列表 S 的元素的重新排列，使其與 S 自身形成一一對應。在一個包含 n 個元素的集合上的排列數由 n! 給出（n 階乘；Uspensky 1937, p. 18）。例如，2!=2·1=2 種 {1,2} 的排列，即 {1,2} 和 {2,1}，以及 3!=3·2·1=6 種 {1,2,3} 的排列，即 {1,2,3}、{1,3,2}、{2,1,3}、{2,3,1}、{3,1,2} 和 {3,2,1}。Wolfram 語言中可以使用以下命令找到列表的排列排列[list]。可以使用以下命令在 Wolfram 語言中測試長度為 n 的列表是否是 1, ..., n 的排列PermutationListQ[list]。

Sedgewick (1977) 總結了許多生成排列的演算法，並指出 Heap (1963) 的最小更改排列演算法通常是最快的（Skiena 1990, p. 10）。Johnson (1963; Séroul 2000, pp. 213-218) 給出了另一種列舉排列的方法。

從一個包含 n 個元素的集合中獲得 k 個元素的有序子集的方式的數量由下式給出

_nP_k=(n!)/((n-k)!)
(1)

(Uspensky 1937, p. 18)，其中 n! 是階乘。例如，4!/2!=12 種 {1,2,3,4} 的 2-子集，即 {1,2}、{1,3}、{1,4}、{2,1}、{2,3}、{2,4}、{3,1}、{3,2}、{3,4}、{4,1}、{4,2} 和 {4,3}。包含 k 個元素的無序子集被稱為給定集合的 k-子集。

將排列表示為置換環的乘積是唯一的（直到迴圈的順序）。迴圈分解的一個例子是 {4,2,1,3} 對 {1,2,3,4} 的排列。這表示為 (2)(143)，對應於不相交的置換環 (2) 和 (143)。在選擇迴圈分解的表示形式時有很大的自由度，因為 (1) 迴圈是不相交的，因此可以按任何順序指定，並且 (2) 給定迴圈的任何旋轉都指定相同的迴圈（Skiena 1990, p. 20）。因此，(431)(2)、(314)(2)、(143)(2)、(2)(431)、(2)(314) 和 (2)(143) 都描述了相同的排列。

另一種表示法明確地標識了應用在 n 個元素上的排列之前和之後元素所佔據的位置，它使用一個 2×n 矩陣，其中第一行是 (123...n)，第二行是新的排列。例如，交換元素 1 和 2 並固定 3 的排列可以寫成

[1 2 3; 2 1 3].
(2)

任何排列也是對換的乘積。排列通常以字典序或對換序表示。排列與一對楊氏 tableau 之間存在對應關係，稱為 Schensted 對應。

n 個物件的錯誤排列數為 [n!/e]，其中 [x] 是最近整數函式。在 n 個有序物件中，沒有物件在其自然位置的排列稱為錯位排列（或有時，完全排列），並且此類排列的數量由次階乘 !n 給出。

使用

(x+y)^n=sum_(r=0)^n(n; r)x^(n-r)y^r
(3)

其中 x=y=1 給出

2^n=sum_(r=0)^n(n; r),
(4)

因此，一次選擇 0、1、... 或 n 個元素的方式的數量是 2^n。

可以使用以下遞迴過程獲得集合 1, ..., n 的所有排列

1 2; / ; 2 1
(5)
1 2 3; / ; 1 3 2 ; / ; 3 1 2 ; | ; 3 2 1 ; \ ; 2 3 1 ; \ ; 2 1 3
(6)

考慮其中沒有連續元素對（即，上升或下降的連續）出現的排列。對於 n=1, 2, ... 個元素，此類排列的數量為 1, 0, 0, 2, 14, 90, 646, 5242, 47622, ... (OEIS A002464)。

設 整數 集合 1, 2, ..., N 被排列，並且得到的序列被分成遞增的遊程。當 n 接近 無窮大 時，將第 n 個遊程的平均長度表示為 N，L_n。前幾個值總結在下表中，其中 e 是自然對數的底數（Le Lionnais 1983, pp. 41-42；Knuth 1998）。

nL_nOEIS近似值
1e-1A0911311.7182818...
2e^2-2eA0911321.9524...
3e^3-3e^2+3/2eA0911331.9957...

另請參見

交錯排列, 取球, 二項式係數, 選擇, 圓排列, 組合, 錯位排列, 尤拉數, 偶排列, k-子集, 線性擴充套件, 夫妻就座問題, 多重選擇, 多項式係數, 多重集, 奇排列, 排列上升, 置換環, 排列倒置, 排列矩陣, 排列模式, 排列遊程, 排列符號, 隨機排列, 字串, 次階乘, 對換 在 課堂中探索此主題

使用 探索

參考文獻

Bogomolny, A. "Graphs." http://www.cut-the-knot.org/do_you_know/permutation.shtml.Conway, J. H. and Guy, R. K. "Arrangement Numbers." In The Book of Numbers. New York: Springer-Verlag, p. 66, 1996.Dickau, R. M. "Permutation Diagrams." http://mathforum.org/advanced/robertd/permutations.html.Heap, B. R. "Permutations by Interchanges." Computer J. 6, 293-294, 1963.Johnson, S. M. "Generation of Permutations by Adjacent Transpositions." Math. Comput. 17, 282-285, 1963.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, pp. 38-43, 1998.Kraitchik, M. "The Linear Permutations of n Different Things." §10.1 in Mathematical Recreations. New York: W. W. Norton, pp. 239-240, 1942.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, 1983.Ruskey, F. "Information on Permutations." http://www.theory.csc.uvic.ca/~cos/inf/perm/PermInfo.html.Sedgewick, R. "Permutation Generation Methods." Comput. Surveys 9, 137-164, 1977.Séroul, R. "Permutations: Johnson's' [sic] Algorithm." §8.15 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 213-218, 2000.Skiena, S. "Permutations." §1.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 3-16, 1990.Sloane, N. J. A. Sequences A000142/M1675, A002464/M2070, A091131, A091132, and A091133 in "The On-Line Encyclopedia of Integer Sequences."Trotter, H. F. "Perm (Algorithm 115)." Comm. ACM 5, 434-435, 1962.Uspensky, J. V. Introduction to Mathematical Probability. New York: McGraw-Hill, p. 18, 1937.

在 上被引用

排列

請引用為

Weisstein, Eric W. "排列。" 來自 Web 資源。 https://mathworld.tw/Permutation.html

主題分類