TOPICS
Search

Permutation


A permutation, also called an "arrangement number" or "order," is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. The number of permutations on a set of n elements is given by n! (n factorial; Uspensky 1937, p. 18). For example, there are 2!=2·1=2 permutations of {1,2}, namely {1,2} and {2,1}, and 3!=3·2·1=6 permutations of {1,2,3}, namely {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, and {3,2,1}. The permutations of a list can be found in the Wolfram Language using the command Permutations[list]. A list of length n can be tested to see if it is a permutation of 1, ..., n in the Wolfram Language using the command PermutationListQ[list].

Sedgewick (1977) summarizes a number of algorithms for generating permutations, and identifies the minimum change permutation algorithm of Heap (1963) to be generally the fastest (Skiena 1990, p. 10). Another method of enumerating permutations was given by Johnson (1963; Séroul 2000, pp. 213-218).

The number of ways of obtaining an ordered subset of k elements from a set of n elements is given by

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

(Uspensky 1937, p. 18), where n! is a factorial. For example, there are 4!/2!=12 2-subsets of {1,2,3,4}, namely {1,2}, {1,3}, {1,4}, {2,1}, {2,3}, {2,4}, {3,1}, {3,2}, {3,4}, {4,1}, {4,2}, and {4,3}. The unordered subsets containing k elements are known as the k-subsets of a given set.

A representation of a permutation as a product of permutation cycles is unique (up to the ordering of the cycles). An example of a cyclic decomposition is the permutation {4,2,1,3} of {1,2,3,4}. This is denoted (2)(143), corresponding to the disjoint permutation cycles (2) and (143). There is a great deal of freedom in picking the representation of a cyclic decomposition since (1) the cycles are disjoint and can therefore be specified in any order, and (2) any rotation of a given cycle specifies the same cycle (Skiena 1990, p. 20). Therefore, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314), and (2)(143) all describe the same permutation.

Another notation that explicitly identifies the positions occupied by elements before and after application of a permutation on n elements uses a 2×n matrix, where the first row is (123...n) and the second row is the new arrangement. For example, the permutation which switches elements 1 and 2 and fixes 3 would be written as

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

Any permutation is also a product of transpositions. Permutations are commonly denoted in lexicographic or transposition order. There is a correspondence between a permutation and a pair of Young tableaux known as the Schensted correspondence.

The number of wrong permutations of n objects is [n!/e] where [x] is the nearest integer function. A permutation of n ordered objects in which no object is in its natural place is called a derangement (or sometimes, a complete permutation) and the number of such permutations is given by the subfactorial !n.

Using

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

with x=y=1 gives

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

so the number of ways of choosing 0, 1, ..., or n at a time is 2^n.

The set of all permutations of a set of elements 1, ..., n can be obtained using the following recursive procedure

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

Consider permutations in which no pair of consecutive elements (i.e., rising or falling successions) occur. For n=1, 2, ... elements, the numbers of such permutations are 1, 0, 0, 2, 14, 90, 646, 5242, 47622, ... (OEIS A002464).

Let the set of integers 1, 2, ..., N be permuted and the resulting sequence be divided into increasing runs. Denote the average length of the nth run as N approaches infinity, L_n. The first few values are summarized in the following table, where e is the base of the natural logarithm (Le Lionnais 1983, pp. 41-42; Knuth 1998).

nL_nOEISapproximate
1e-1A0911311.7182818...
2e^2-2eA0911321.9524...
3e^3-3e^2+3/2eA0911331.9957...

See also

Alternating Permutation, Ball Picking, Binomial Coefficient, Choose, Circular Permutation, Combination, Derangement, Eulerian Number, Even Permutation, k-Subset, Linear Extension, Married Couples Problem, Multichoose, Multinomial Coefficient, Multiset, Odd Permutation, Permutation Ascent, Permutation Cycle, Permutation Inversion, Permutation Matrix, Permutation Pattern, Permutation Run, Permutation Symbol, Random Permutation, String, Subfactorial, Transposition Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

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.

Referenced on Wolfram|Alpha

Permutation

Cite this as:

Weisstein, Eric W. "Permutation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Permutation.html

Subject classifications