A permutation of a set 
is a one-to-one correspondence
of 
with itself. For a finite
set, it can be represented by an ordered arrangement of its distinct elements,
also called an "arrangement number" or "order." 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).
For integers 
, the number of ordered selections of 
distinct elements from a set of 
elements is given by
 |
(1)
|
(Uspensky 1937, p. 18), where 
is a factorial. For example,
there are 
ordered selections of two elements from 
, namely 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, and 
. The subsets containing 
elements are known as the k-subsets
of a given set.
A representation of a permutation as a product of disjoint permutation cycles is unique up to the ordering
of the cycles and cyclic rotation within each cycle. An example 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. The Schensted
correspondence is a bijection between permutations
of 1, ..., 
and pairs of standard Young tableaux of the same
shape.
For a positive integer 
, the number of wrong permutations of 
objects is ![[n!/e]](/images/equations/Permutation/Inline48.svg)
where ![[x]](/images/equations/Permutation/Inline49.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 the 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).
Choose uniformly among permutations of the set of integers 1, 2, ..., 
,
producing a random permutation, and divide
the resulting sequence 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