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, ..., 
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 
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
![[1 2 3; 2 1 3].](/images/equations/Permutation/NumberedEquation2.svg) |
(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 ![[n!/e]](/images/equations/Permutation/Inline45.svg)
where ![[x]](/images/equations/Permutation/Inline46.svg)
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).
Different Things." §10.1 in