, a permutation of a set
is, loosely speaking, an arrangement of its members into a sequence
or linear order
, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.
Permutations differ from combination
s, which are selections of some members of a set regardless of order. For example, written as tuple
s, there are six permutations of the set , namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three-element set. Anagram
s of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. The study of permutations of finite set
s is an important topic in the fields of combinatorics
and group theory
Permutations are used in almost every branch of mathematics, and in many other fields of science. In computer science
, they are used for analyzing sorting algorithm
s; in quantum physics
, for describing states of particles; and in biology
, for describing RNA
The number of permutations of distinct objects is factorial
, usually written as , which means the product of all positive integers less than or equal to .
Technically, a permutation of a set
is defined as a bijection
from to itself. That is, it is a function
from to for which every element occurs exactly once as an image
value. This is related to the rearrangement of the elements of in which each element is replaced by the corresponding . For example, the permutation (3,1,2) mentioned above is described by the function
The collection of all permutations of a set form a group
called the symmetric group
of the set. The group operation is the composition
(performing two given rearrangements in succession), which results in another rearrangement. As properties of permutations do not depend on the nature of the set elements, it is often the permutations of the set
that are considered for studying permutations.
In elementary combinatorics, the -permutations, or partial permutation
s, are the ordered arrangements of distinct elements selected from a set. When is equal to the size of the set, these are the permutations of the set.
invented in 1974 by Ernő Rubik
, each turn of the puzzle faces creates a permutation of the surface colors.]]
Permutations called Hexagram (I Ching)|hexagrams
were used in China in the I Ching
: Yi Jing) as early as 1000 BC.
(717–786), an Arab mathematician
, wrote the ''Book of Cryptographic Messages''. It contains the first use of permutations and combinations
, to list all possible Arabic
words with and without vowels.
The rule to determine the number of permutations of ''n'' objects was known in Indian culture around 1150. The ''Lilavati
'' by the Indian mathematician Bhaskara II
contains a passage that translates to:
The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.
In 1677, Fabian Stedman
described factorials when explaining the number of permutations of bells in change ringing
. Starting from two bells: "first, ''two'' must be admitted to be varied in two ways", which he illustrates by showing 1 2 and 2 1. He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. His explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast away 1, and 2.3 will remain". He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Effectively, this is a recursive process. He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations. At this point he gives up and remarks:
Now the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers, ... insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body;
Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20.
A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when Joseph Louis Lagrange
, in the study of polynomial equations, observed that properties of the permutations of the roots
of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of Évariste Galois
, in Galois theory
, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics, there are many similar situations in which understanding a problem requires studying certain permutations related to it.
Permutations without repetitions
The simplest example of permutations is permutations without repetitions where we consider the number of possible ways of arranging items into places. The factorial
has special application in defining the number of permutations in a set which does not include repetitions. The number n!, read "n factorial", is precisely the number of ways we can rearrange n things into a new order. For example, if we have three fruit: an orange, apple and pear, we can eat them in the order mentioned, or we can change them (for example, an apple, a pear then an orange). The exact number of permutations is then
. The number gets extremely large as the number of items (n) goes up.
In a similar manner, the number of arrangements of r items from n objects is consider a partial permutation. It is written as
(which reads "n permute r"), and is equal to the number
(also written as
In mathematics texts it is customary to denote permutations using lowercase Greek letters. Commonly, either
Permutations can be defined as bijections from a set onto itself. All permutations of a set with ''n'' elements form a symmetric group
, where the group operation
is function composition
. Thus for two permutations,
in the group
, the four group axioms hold:
then so is
: For any three permutations
: There is an identity permutation, denoted
and defined by
. For any
: For every permutation
, there exists
In general, composition of two permutations is not commutative
, that is,
As a bijection from a set to itself, a permutation is a function that ''performs'' a rearrangement of a set, and is not a rearrangement itself. An older and more elementary viewpoint is that permutations are the rearrangements themselves. To distinguish between these two, the identifiers ''active'' and ''passive'' are sometimes prefixed to the term ''permutation'', whereas in older terminology ''substitutions'' and ''permutations'' are used.
A permutation can be decomposed into one or more disjoint ''cycles'', that is, the orbits
, which are found by repeatedly tracing the application of the permutation on some elements. For example, the permutation
has a 1-cycle,
while the permutation
has a 2-cycle
(for details on the syntax, see below). In general, a cycle of length ''k'', that is, consisting of ''k'' elements, is called a ''k''-cycle.
An element in a 1-cycle
is called a fixed point
of the permutation. A permutation with no fixed points is called a derangement
. 2-cycles are called transpositions
; such permutations merely exchange two elements, leaving the others fixed.
Since writing permutations elementwise, that is, as piecewise
functions, is cumbersome, several notations have been invented to represent them more compactly. ''Cycle notation'' is a popular choice for many mathematicians due to its compactness and the fact that it makes a permutation's structure transparent. It is the notation used in this article unless otherwise specified, but other notations are still widely used, especially in application areas.
's ''two-line notation'', one lists the elements of ''S'' in the first row, and for each one its image below it in the second row. For instance, a particular permutation of the set ''S'' = can be written as:
this means that ''σ'' satisfies , , , , and . The elements of ''S'' may appear in any order in the first row. This permutation could also be written as:
If there is a "natural" order for the elements of ''S'', say
, then one uses this for the first row of the two-line notation:
Under this assumption, one may omit the first row and write the permutation in ''one-line notation'' as
that is, an ordered arrangement of S. Care must be taken to distinguish one-line notation from the cycle notation
described below. In mathematics literature, a common usage is to omit parentheses for one-line notation, while using them for cycle notation. The one-line notation is also called the ''word
representation'' of a permutation.
The example above would then be 2 5 4 3 1 since the natural order 1 2 3 4 5 would be assumed for the first row. (It is typical to use commas to separate these entries only if some have two or more digits.) This form is more compact, and is common in elementary combinatorics
and computer science
. It is especially useful in applications where the elements of ''S'' or the permutations are to be compared as larger or smaller.
Cycle notation describes the effect of repeatedly applying the permutation on the elements of the set. It expresses the permutation as a product of cycles
; since distinct cycles are disjoint
, this is referred to as "decomposition into disjoint cycles".
To write down the permutation
in cycle notation, one proceeds as follows:
# Write an opening bracket then select an arbitrary element ''x'' of
and write it down:
# Then trace the orbit of ''x''; that is, write down its values under successive applications of
# Repeat until the value returns to ''x'' and write down a closing parenthesis rather than ''x'':
# Now continue with an element ''y'' of ''S'', not yet written down, and proceed in the same way:
# Repeat until all elements of ''S'' are written in cycles.
Since for every new cycle the starting point can be chosen in different ways, there are in general many different cycle notations for the same permutation; for the example above one has:
1-cycles are often omitted from the cycle notation, provided that the context is clear; for any element ''x'' in ''S'' not appearing in any cycle, one implicitly assumes
. The identity permutation
, which consists only of 1-cycles, can be denoted by a single 1-cycle (x), by the number 1, or by ''id''.
A convenient feature of cycle notation is that one can find a permutation's inverse simply by reversing the order of the elements in the permutation's cycles. For example
Canonical cycle notation ( standard form)
In some combinatorial contexts it is useful to fix a certain order for the elements in the cycles and of the (disjoint) cycles themselves. Miklós Bóna
calls the following ordering choices the ''canonical cycle notation'':
* in each cycle the ''largest'' element is listed first
* the cycles are sorted in ''increasing'' order of their first element
For example, (312)(54)(8)(976) is a permutation in canonical cycle notation. The canonical cycle notation does not omit one-cycles.
Richard P. Stanley
calls the same choice of representation the "standard representation" of a permutation.
and Martin Aigner uses the term "standard form" for the same notion.
Sergey Kitaev also uses the "standard form" terminology, but reverses both choices; that is, each cycle lists its least element first and the cycles are sorted in decreasing order of their least, that is, first elements.
Composition of permutations
There are two ways to denote the composition of two permutations.
is the function that maps any element ''x'' of the set to
. The rightmost permutation is applied to the argument first,
because of the way the function application is written.
Since function composition
, so is the composition operation on permutations:
. Therefore, products of more than two permutations are usually written without adding parentheses to express grouping; they are also usually written without a dot or other sign to indicate composition.
Some authors prefer the leftmost factor acting first,
but to that end permutations must be written to the ''right'' of their argument, often as an exponent, where ''σ'' acting on ''x'' is written ''x''''σ''
; then the product is defined by . However this gives a ''different'' rule for multiplying permutations; this article uses the definition where the rightmost permutation is applied first.
Other uses of the term ''permutation''
The concept of a permutation as an ordered arrangement admits several generalizations that are not permutations, but have been called permutations in the literature.
''k''-permutations of ''n''
A weaker meaning of the term ''permutation'', sometimes used in elementary combinatorics texts, designates those ordered arrangements in which no element occurs more than once, but without the requirement of using all the elements from a given set. These are not permutations except in special cases, but are natural generalizations of the ordered arrangement concept. Indeed, this use often involves considering arrangements of a fixed length ''k'' of elements taken from a given set of size ''n'', in other words, these ''k''-permutations of ''n'' are the different ordered arrangements of a ''k''-element subset of an ''n''-set (sometimes called variations or arrangements in the older literature). These objects are also known as partial permutations
or as sequences without repetition, terms that avoid confusion with the other, more common, meaning of "permutation". The number of such
is denoted variously by such symbols as
, and its value is given by the product
which is 0 when , and otherwise is equal to
The product is well defined without the assumption that
is a non-negative integer, and is of importance outside combinatorics as well; it is known as the Pochhammer symbol
or as the
-th falling factorial power
This usage of the term ''permutation'' is closely related to the term ''combination
''. A ''k''-element combination of an ''n''-set ''S'' is a ''k'' element subset of ''S'', the elements of which are not ordered. By taking all the ''k'' element subsets of ''S'' and ordering each of them in all possible ways, we obtain all the ''k''-permutations of ''S''. The number of ''k''-combinations of an ''n''-set, ''C''(''n'',''k''), is therefore related to the number of ''k''-permutations of ''n'' by:
These numbers are also known as binomial coefficient
s and are denoted by
Permutations with repetition
Ordered arrangements of ''n'' elements of a set ''S'', where repetition is allowed, are called ''n''-tuples
. They have sometimes been referred to as permutations with repetition, although they are not permutations in general. They are also called words
over the alphabet ''S'' in some contexts. If the set ''S'' has ''k'' elements, the number of ''n''-tuples over ''S'' is
There is no restriction on how often an element can appear in an ''n''-tuple, but if restrictions are placed on how often an element can appear, this formula is no longer valid.
Permutations of multisets
If ''M'' is a finite multiset
, then a multiset permutation is an ordered arrangement of elements of ''M'' in which each element appears a number of times equal exactly to its multiplicity in ''M''. An anagram
of a word having some repeated letters is an example of a multiset permutation. If the multiplicities of the elements of ''M'' (taken in some order) are
and their sum (that is, the size of ''M'') is ''n'', then the number of multiset permutations of ''M'' is given by the multinomial coefficient
For example, the number of distinct anagrams of the word MISSISSIPPI is:
A k-permutation of a multiset ''M'' is a sequence of length ''k'' of elements of ''M'' in which each element appears ''a number of times less than or equal to'' its multiplicity in ''M'' (an element's ''repetition number'').
Permutations, when considered as arrangements, are sometimes referred to as ''linearly ordered'' arrangements. In these arrangements there is a first element, a second element, and so on. If, however, the objects are arranged in a circular manner this distinguished ordering no longer exists, that is, there is no "first element" in the arrangement, any element can be considered as the start of the arrangement. The arrangements of objects in a circular manner are called circular permutations. These can be formally defined as equivalence classes
of ordinary permutations of the objects, for the equivalence relation
generated by moving the final element of the linear arrangement to its front.
Two circular permutations are equivalent if one can be rotated into the other (that is, cycled without changing the relative positions of the elements). The following two circular permutations on four letters are considered to be the same.
4 3 2 1
The circular arrangements are to be read counterclockwise, so the following two are not equivalent since no rotation can bring one to the other.
4 3 3 4
The number of circular permutations of a set ''S'' with ''n'' elements is (''n'' – 1)!.
The number of permutations of distinct objects is !.
The number of -permutations with disjoint cycles is the signless Stirling number of the first kind
, denoted by .
The cycles of a permutation partition the set
so the lengths of the cycles of a permutation
form a partition
of ''n'' called the cycle type
. There is a "1" in the cycle type for every fixed point of σ, a "2" for every transposition, and so on. The cycle type of
is (3,2,2,1) which is sometimes written in a more compact form as 12231
The general form is