主题
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-子集, 线性扩展, 夫妻就座问题, 多重选择, 多项式系数, 多重集, 奇排列, 排列上升, 置换环, 排列倒置, 排列矩阵, 排列模式, 排列游程, 排列符号, 随机排列, 字符串, 次阶乘, 对换 在 MathWorld 课堂中探索此主题

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

排列

请引用为

Weisstein, Eric W. "排列。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Permutation.html

主题分类