Permutation

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

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 elements from a set of elements is given by

(1)

(Uspensky 1937, p. 18), where is a factorial. For example, there are 2-subsets of , namely , , , , , , , , , , , and . The unordered subsets containing 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 of . This is denoted , 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 elements uses a matrix, where the first row is 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

(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 objects is where is the nearest integer function. A permutation of 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 .

Using

(3)

with gives

(4)

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

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

(5)

(6)

Consider permutations in which no pair of consecutive elements (i.e., rising or falling successions) occur. For , 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, ..., be permuted and the resulting sequence be divided into increasing runs. Denote the average length of the th run as approaches infinity, . 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).

		Sloane	approximate
1		A091131	1.7182818...
2		A091132	1.9524...
3		A091133	1.9957...

Wolfram Web Resources