HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a permutation of a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
is, loosely speaking, an arrangement of its members into a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
or
linear order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive ...
, 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 In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
s, which are selections of some members of a set regardless of order. For example, written as
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
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 An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, the word ''anagram'' itself can be rearranged into ''nag a ram'', also the word ...
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 In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...
s is an important topic in the fields of
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
and
group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
. Permutations are used in almost every branch of mathematics, and in many other fields of science. In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, they are used for analyzing
sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. ...
s; in
quantum physics Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, qua ...
, for describing states of particles; and in
biology Biology is the scientific study of life. It is a natural science with a broad scope but has several unifying themes that tie it together as a single, coherent field. For instance, all organisms are made up of cells that process hereditary i ...
, for describing
RNA Ribonucleic acid (RNA) is a polymeric molecule essential in various biological roles in coding, decoding, regulation and expression of genes. RNA and deoxyribonucleic acid ( DNA) are nucleic acids. Along with lipids, proteins, and carbohydra ...
sequences. The number of permutations of distinct objects is  
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
, usually written as , which means the product of all positive integers less than or equal to . Technically, a permutation of a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
is defined as a
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
from to itself. That is, it is a
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
from to for which every element occurs exactly once as an
image An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
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 \alpha defined as : \alpha(1) = 3, \quad \alpha(2) = 1, \quad \alpha(3) = 2. The collection of all permutations of a set form a
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...
called the
symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
of the set. The group operation is the
composition Composition or Compositions may refer to: Arts and literature *Composition (dance), practice and teaching of choreography *Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
(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 In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set ''S'' is a bijection between two specified subsets of ''S''. That is, it is defined by two subsets ''U'' and ''V'' of equal size, and a one-to-one m ...
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.


History

Permutations called
hexagrams , can be seen as a compound composed of an upwards (blue here) and downwards (pink) facing equilateral triangle, with their intersection as a regular hexagon (in green). A hexagram ( Greek language, Greek) or sexagram (Latin) is a six-pointed ...
were used in China in the
I Ching The ''I Ching'' or ''Yi Jing'' (, ), usually translated ''Book of Changes'' or ''Classic of Changes'', is an ancient Chinese divination text that is among the oldest of the Chinese classics. Originally a divination manual in the Western Zho ...
(
Pinyin Hanyu Pinyin (), often shortened to just pinyin, is the official romanization system for Standard Mandarin Chinese in China, and to some extent, in Singapore and Malaysia. It is often used to teach Mandarin, normally written in Chinese for ...
: Yi Jing) as early as 1000 BC.
Al-Khalil Hebron ( ar, الخليل or ; he, חֶבְרוֹן ) is a Palestinian. city in the southern West Bank, south of Jerusalem. Nestled in the Judaean Mountains, it lies above sea level. The second-largest city in the West Bank (after East J ...
(717–786), an Arab mathematician and
cryptographer Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, wrote the ''Book of Cryptographic Messages''. It contains the first use of permutations and combinations, to list all possible
Arabic Arabic (, ' ; , ' or ) is a Semitic languages, Semitic language spoken primarily across the Arab world.Semitic languages: an international handbook / edited by Stefan Weninger; in collaboration with Geoffrey Khan, Michael P. Streck, Janet C ...
words with and without vowels. The rule to determine the number of permutations of ''n'' objects was known in Indian culture around 1150 AD. 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 Fabian Stedman (1640–1713) was an English author and a leading figure in the early history of campanology, particularly in the field of method ringing. He had a key role in publishing two books ''Tintinnalogia'' (1668 with Richard Duckworth) and ...
described factorials when explaining the number of permutations of bells in
change ringing Change ringing is the art of ringing a set of tuned bells in a tightly controlled manner to produce precise variations in their successive striking sequences, known as "changes". This can be by method ringing in which the ringers commit to memor ...
. 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 Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangiaroots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusing ...
of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of
Évariste Galois Évariste Galois (; ; 25 October 1811 – 31 May 1832) was a French mathematician and political activist. While still in his teens, he was able to determine a necessary and sufficient condition for a polynomial to be solvable by radicals, ...
, in
Galois theory In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
, 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 In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
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 fruits: 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 3! = 1 \cdot 2 \cdot 3 = 6. The number gets extremely large as the number of items (n) goes up. In a similar manner, the number of arrangements of k items from n objects is sometimes called a
partial permutation In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set ''S'' is a bijection between two specified subsets of ''S''. That is, it is defined by two subsets ''U'' and ''V'' of equal size, and a one-to-one m ...
or a
k-permutation In mathematics, 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 proc ...
. It can be written as nPk (which reads "n permute k"), and is equal to the number n (n-1) \cdots (n - k + 1) (also written as


Definition

In mathematics texts it is customary to denote permutations using lowercase Greek letters. Commonly, either \alpha and \beta, or \sigma, \tau and \pi are used. Permutations can be defined as bijections from a set onto itself. All permutations of a set with ''n'' elements form a
symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
, denoted S_n, where the
group operation In mathematics, a group is a set and an operation that combines any two elements of the set to produce a third element of the set, in such a way that the operation is associative, an identity element exists and every element has an inverse. Thes ...
is
function composition In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
. Thus for two permutations, \pi and \sigma in the group S_n, the four group axioms hold: # Closure: If \pi and \sigma are in S_n then so is \pi\sigma. #
Associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
: For any three permutations \pi, \sigma, \tau \in S_n, (\pi\sigma)\tau = \pi(\sigma\tau). #
Identity Identity may refer to: * Identity document * Identity (philosophy) * Identity (social science) * Identity (mathematics) Arts and entertainment Film and television * ''Identity'' (1987 film), an Iranian film * ''Identity'' (2003 film), ...
: There is an identity permutation, denoted \operatorname and defined by \operatorname(x) = x for all x \in S. For any \sigma \in S_n, \operatorname \sigma = \sigma \operatorname = \sigma. # Invertibility: For every permutation \pi \in S_n, there exists an inverse permutation \pi^ \in S_n, so that \pi\pi^ = \pi^\pi = \operatorname. In general, composition of two permutations is not
commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
, that is, \pi\sigma \neq \sigma\pi. As a bijection from a set to itself, a permutation is a function that ''performs'' a rearrangement of a set, and is not an arrangement itself. An older and more elementary viewpoint is that permutations are the arrangements 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 In celestial mechanics, an orbit is the curved trajectory of an object such as the trajectory of a planet around a star, or of a natural satellite around a planet, or of an artificial satellite around an object or position in space such as a p ...
, which are found by repeatedly tracing the application of the permutation on some elements. For example, the permutation \sigma defined by \sigma(7) = 7 has a 1-cycle, (\,7\,) while the permutation \pi defined by \pi(2) = 3 and \pi(3) = 2 has a 2-cycle (\,2\,3\,) (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 (\,x\,) is called a fixed point of the permutation. A permutation with no fixed points is called a
derangement In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points. The number of derangements of ...
. 2-cycles are called transpositions; such permutations merely exchange two elements, leaving the others fixed.


Notations

Since writing permutations elementwise, that is, as
piecewise In mathematics, a piecewise-defined function (also called a piecewise function, a hybrid function, or definition by cases) is a function defined by multiple sub-functions, where each sub-function applies to a different interval in the domain. Pi ...
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.


Two-line notation

In
Cauchy Baron Augustin-Louis Cauchy (, ; ; 21 August 178923 May 1857) was a French mathematician, engineer, and physicist who made pioneering contributions to several branches of mathematics, including mathematical analysis and continuum mechanics. He w ...
'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 : \sigma = \begin 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \end; 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: : \sigma = \begin 3 & 2 & 5 & 1 & 4 \\ 4 & 5 & 1 & 2 & 3 \end, or : \sigma = \begin 5 & 1 & 4 & 3 & 2 \\ 1 & 2 & 3 & 4 & 5 \end.


One-line notation

If there is a "natural" order for the elements of ''S'', say x_1, x_2, \ldots, x_n, then one uses this for the first row of the two-line notation: : \sigma = \begin x_1 & x_2 & x_3 & \cdots & x_n \\ \sigma(x_1) & \sigma(x_2) & \sigma(x_3) & \cdots & \sigma(x_n) \end. Under this assumption, one may omit the first row and write the permutation in ''one-line notation'' as : (\sigma(x_1) \; \sigma(x_2) \; \sigma(x_3) \; \cdots \; \sigma(x_n)) , that is, as an ordered arrangement of the elements 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 A word is a basic element of language that carries an semantics, objective or pragmatics, practical semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of w ...
representation'' of a permutation. The example above would then be since the natural order 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 Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
. It is especially useful in applications where the elements of ''S'' or the permutations are to be compared as larger or smaller.


Cycle notation

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 \sigma in cycle notation, one proceeds as follows: # Write an opening bracket then select an arbitrary element ''x'' of S and write it down: (\,x # Then trace the orbit of ''x''; that is, write down its values under successive applications of \sigma: (\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots # Repeat until the value returns to ''x'' and write down a closing parenthesis rather than ''x'': (\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,) # Now continue with an element ''y'' of ''S'', not yet written down, and proceed in the same way: (\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)(\,y\,\ldots\,) # Repeat until all elements of ''S'' are written in cycles. So the permutation (in one-line notation) could be written as in cycle notation. While permutations in general do not commute, disjoint cycles do; for example, (\,1 \, 2 \, 5\,) (\,3\,4\,) = (\,3 \, 4\,) (\,1 \, 2 \, 5\,). In addition, each cycle can be written in different ways, by choosing different starting points; for example, (\,1 \, 2 \, 5\,) (\,3\,4\,) = (\,5 \, 1 \, 2\,)(\,3 \, 4\,) = (\,2 \, 5 \, 1\,)(\,4 \, 3\,). One may combine these equalities to write the disjoint cycles of a given permutation in many different ways. 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 \sigma(x) = x. The
identity permutation In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to its ...
, 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 cycle notation of the inverse permutation is given by reversing the order of the elements in the permutation's cycles. For example, \,1\,2\,5\,)(\,3\,4\,) = (\,5\,2\,1\,)(\,4\,3\,).


Canonical cycle notation

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 Miklós Bóna (born October 6, 1967, in Székesfehérvár) is an American mathematician of Hungarian origin. Bóna completed his undergraduate studies in Budapest and Paris, then obtained his Ph.D. at MIT in 1997 as a student of Richard P. Sta ...
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 Richard Peter Stanley (born June 23, 1944) is an Emeritus Professor of Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. From 2000 to 2010, he was the Norman Levinson Professor of Applied Mathematics. He r ...
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. \sigma\cdot \pi is the function that maps any element ''x'' of the set to \sigma(\pi(x)). The rightmost permutation is applied to the argument first, because of the way the function application is written. Since
function composition In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
is
associative In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
, so is the composition operation on permutations: (\sigma\pi)\tau = \sigma(\pi\tau). 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 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 k-permutations of n is denoted variously by such symbols as P^n_k, _nP_k, ^nP_k, P_, or P(n,k), and its value is given by the product : P(n,k) = \underbrace_, which is 0 when , and otherwise is equal to : \frac. The product is well defined without the assumption that n is a non-negative integer, and is of importance outside combinatorics as well; it is known as the
Pochhammer symbol In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial :\begin (x)_n = x^\underline &= \overbrace^ \\ &= \prod_^n(x-k+1) = \prod_^(x-k) \,. \e ...
(n)_k or as the k-th falling factorial power n^ of n. This usage of the term ''permutation'' is closely related to the term ''
combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
''. 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: : C(n,k) = \frac = \frac = \frac. These numbers are also known as
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s and are denoted by \binom.


Permutations with repetition

Ordered arrangements of ''k'' elements of a set ''S'', where repetition is allowed, are called ''k''-tuples. They have sometimes been referred to as permutations with repetition, although they are not permutations in general. They are also called
words A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consen ...
over the alphabet ''S'' in some contexts. If the set ''S'' has ''n'' elements, the number of ''k''-tuples over ''S'' is n^k. There is no restriction on how often an element can appear in an ''k''-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 In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
, 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 An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, the word ''anagram'' itself can be rearranged into ''nag a ram'', also the word ...
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 m_1, m_2, ..., m_l 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 In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials. Theorem For any positive integer an ...
, : = \frac = \frac. For example, the number of distinct anagrams of the word MISSISSIPPI is: :\frac = 34650. 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'').


Circular permutations

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 In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
of ordinary permutations of the objects, for the
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each 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 four circular permutations on four letters are considered to be the same.
     1           4           2           3
   4   3       2   1       3   4       1   2
     2           3           1           4
The circular arrangements are to be read counter-clockwise, so the following two are not equivalent since no rotation can bring one to the other.
     1          1
   4   3      3   4
     2          2
The number of circular permutations of a set ''S'' with ''n'' elements is (''n'' – 1)!.


Properties

The number of permutations of distinct objects is !. The number of -permutations with disjoint cycles is the signless
Stirling number of the first kind In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed poin ...
, denoted by .


Cycle type

The cycles (including the fixed points) of a permutation \sigma of a set with elements partition that set; so the lengths of these cycles form an
integer partition In number theory and combinatorics, a partition of a positive integer , also called an integer partition, is a way of writing as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same part ...
of , which is called the cycle type (or sometimes cycle structure or cycle shape) of \sigma. There is a "1" in the cycle type for every fixed point of \sigma, a "2" for every transposition, and so on. The cycle type of \beta = (1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,) is (3, 2, 2, 1). This may also be written in a more compact form as . More precisely, the general form is ^2^\dotsm n^/math>, where \alpha_1,\ldots,\alpha_n are the numbers of cycles of respective length. The number of permutations of a given cycle type is : \frac.


Conjugating permutations

In general, composing permutations written in cycle notation follows no easily described pattern – the cycles of the composition can be different from those being composed. However the cycle type is preserved in the special case of conjugating a permutation \sigma by another permutation \pi, which means forming the product \pi\sigma\pi^. Here, \pi\sigma\pi^ is the ''conjugate'' of \sigma by \pi and its cycle notation can be obtained by taking the cycle notation for \sigma and applying \pi to all the entries in it. It follows that two permutations are conjugate exactly when they have the same cycle type.


Permutation order

The order of a permutation \sigma is the smallest positive integer ''m'' so that \sigma^m = \mathrm. It is the
least common multiple In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bot ...
of its cycles lengths. For example, the order of (\,1\,3\,2)(\,4\,5\,) is 2\cdot3 = 6.


Parity of a permutation

Every permutation of a finite set can be expressed as the product of transpositions. Although many such expressions for a given permutation may exist, either they all contain an even number of transpositions or they all contain an odd number of transpositions. Thus all permutations can be classified as even or odd depending on this number. This result can be extended so as to assign a ''sign'', written \operatorname\sigma, to each permutation. \operatorname\sigma = +1 if \sigma is even and \operatorname\sigma = -1 if \sigma is odd. Then for two permutations \sigma and \pi : \operatorname(\sigma\pi) = \operatorname\sigma\cdot\operatorname\pi. It follows that \operatorname\left(\sigma\sigma^\right) = +1.


Matrix representation

A ''permutation matrix'' is an ''n'' × ''n'' matrix that has exactly one entry 1 in each column and in each row, and all other entries are 0. There are several different conventions that one can use to assign a permutation matrix to a permutation of . One natural approach is to associate to the permutation ''σ'' the matrix M_ whose (''i'', ''j'') entry is 1 if ''i'' = ''σ''(''j'') and is 0 otherwise. This convention has two attractive properties: first, the product of matrices and of permutations is in the same order, that is, M_\sigma M_\pi = M_ for all permutations ''σ'' and ''π''. Second, if _i represents the
standard Standard may refer to: Symbols * Colours, standards and guidons, kinds of military signs * Standard (emblem), a type of a large symbol or emblem used for identification Norms, conventions or requirements * Standard (metrology), an object th ...
n \times 1
column vector In linear algebra, a column vector with m elements is an m \times 1 matrix consisting of a single column of m entries, for example, \boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end. Similarly, a row vector is a 1 \times n matrix for some n, c ...
(the vector with ''i''th entry equal to 1 and all other entries equal to 0), then M_\sigma _i = _. For example, with this convention, the matrix associated to the permutation \sigma(1,2,3)=(2,1,3) is \begin 0&1&0\\1&0&0\\0&0&1\end and the matrix associated to the permutation \pi(1,2,3)=(2,3,1) is \begin 0&0&1\\1&0&0\\0&1&0\end. Then the composition of permutations is (\sigma\circ\pi)(1,2,3)=\sigma(2,3,1)=(1,3,2), and the corresponding matrix product is M_ M_ = \begin 0&1&0\\1&0&0\\0&0&1\end\begin 0&0&1\\1&0&0\\0&1&0\end = \begin 1&0&0\\0&0&1\\0&1&0\end = M_. It is also common in the literature to find the inverse convention, where a permutation ''σ'' is associated to the matrix P_ = (M_)^ = (M_)^ whose (''i'', ''j'') entry is 1 if ''j'' = ''σ''(''i'') and is 0 otherwise. In this convention, permutation matrices multiply in the opposite order from permutations, that is, P_\sigma P_ = P_ for all permutations ''σ'' and ''π''. In this correspondence, permutation matrices act by permuting indices of standard 1 \times n row vectors (_i)^T: one has (_i)^T P_ = (_)^T. The
Cayley table Named after the 19th century British mathematician Arthur Cayley, a Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements in a square table reminiscent of an addition or multiplicat ...
on the right shows these matrices for permutations of 3 elements.


Permutations of totally ordered sets

In some applications, the elements of the set being permuted will be compared with each other. This requires that the set ''S'' has a
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
so that any two elements can be compared. The set is totally ordered by the usual "≤" relation and so it is the most frequently used set in these applications, but in general, any totally ordered set will do. In these applications, the ordered arrangement view of a permutation is needed to talk about the ''positions'' in a permutation. There are a number of properties that are directly related to the total ordering of ''S''.


Ascents, descents, runs and excedances

An ''ascent'' of a permutation ''σ'' of ''n'' is any position ''i'' < ''n'' where the following value is bigger than the current one. That is, if ''σ'' = ''σ''1''σ''2...''σ''''n'', then ''i'' is an ascent if ''σ''''i'' < ''σ''''i''+1. For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6. Similarly, a ''descent'' is a position ''i'' < ''n'' with ''σ''''i'' > ''σ''''i''+1, so every ''i'' with 1 \leq i either is an ascent or is a descent of ''σ''. An ''ascending run'' of a permutation is a nonempty increasing contiguous subsequence of the permutation that cannot be extended at either end; it corresponds to a maximal sequence of successive ascents (the latter may be empty: between two successive descents there is still an ascending run of length 1). By contrast an ''increasing subsequence'' of a permutation is not necessarily contiguous: it is an increasing sequence of elements obtained from the permutation by omitting the values at some positions. For example, the permutation 2453167 has the ascending runs 245, 3, and 167, while it has an increasing subsequence 2367. If a permutation has ''k'' − 1 descents, then it must be the union of ''k'' ascending runs. The number of permutations of ''n'' with ''k'' ascents is (by definition) the
Eulerian number In combinatorics, the Eulerian number ''A''(''n'', ''m'') is the number of permutations of the numbers 1 to ''n'' in which exactly ''m'' elements are greater than the previous element (permutations with ''m'' "ascents"). They are the coefficients ...
\textstyle\left\langle\right\rangle; this is also the number of permutations of ''n'' with ''k'' descents. Some authors however define the Eulerian number \textstyle\left\langle\right\rangle as the number of permutations with ''k'' ascending runs, which corresponds to descents. An excedance of a permutation ''σ''1''σ''2...''σ''''n'' is an index ''j'' such that . If the inequality is not strict (that is, ), then ''j'' is called a ''weak excedance''. The number of ''n''-permutations with ''k'' excedances coincides with the number of ''n''-permutations with ''k'' descents.


Foata's transition lemma

There is a relationship between the one-line notation and the canonical cycle notation. Consider the permutation (\,2\,)(\,3\,1\,) in canonical cycle notation; if we simply remove the parentheses, we obtain the permutation 231 in one-line notation. Foata's transition lemma establishes the nature of this correspondence as a bijection on the set of ''n''-permutations (to itself). Richard P. Stanley calls this correspondence the ''fundamental bijection''. Let f(p)=q be the parentheses-erasing transformation which returns q in one-line notation when given p in canonical cycle notation. As stated, f operates by simply removing all parentheses. The operation of the inverse transformation, f^(q)=p, which returns p in canonical cycle notation when given q in one-line notation, is a bit less intuitive. Given the one-line notation q = q_1q_2\cdots q_n, the first cycle of p in canonical cycle notation must start with q_1. As long as the subsequent elements are smaller than q_1, we are in the same cycle of p. The second cycle of p starts at the smallest index j such that q_j > q_1. In other words, q_j is larger than everything else to its left, so it is called a ''left-to-right maximum''. Every cycle in the canonical cycle notation starts with a left-to-right maximum. For example, in the permutation q=312548976, 5 is the first element larger than the starting element 3, so the first cycle of p must be (\,3\,1\,2\,). Then 8 is the next element larger than 5, so the second cycle is (\,5\,4\,). Since 9 is larger than 8, (\,8\,) is a cycle by itself. Finally, 9 is larger than all the remaining elements to its right, so the last cycle is (\,9\,7\,6\,). Concatenating these 4 cycles gives p=(\,3\,1\,2\,)(\,5\,4\,)(\,8\,)(\,9\,7\,6\,) in canonical cycle notation. The following table shows both q and p for the six permutations of 123. The bold side of each equality shows the permutation using its designated notation (one-line notation for q and canonical cycle notation for p) while the non-bold side shows the same permutation in the other notation. Comparing the bold side of each column of the table shows the parenthesis removing/restoring operation of Foata's bijection, while comparing the same side of each column (for example, the LHS) shows which permutations are mapped to themselves by the bijection (first 3 rows) and which are not (last 3 rows). As a first corollary, the number of n-permutations with exactly ''k'' left-to-right maxima is also equal to the signless
Stirling number of the first kind In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed poin ...
, c(n, k). Furthermore, Foata's mapping takes an ''n''-permutation with ''k''-weak excedances to an ''n''-permutations with ascents. For example, (2)(31) = 321 has two weak excedances (at index 1 and 2), whereas has one ascent (at index 1; that is, from 2 to 3).


Inversions

An ''
inversion Inversion or inversions may refer to: Arts * , a French gay magazine (1924/1925) * ''Inversion'' (artwork), a 2005 temporary sculpture in Houston, Texas * Inversion (music), a term with various meanings in music theory and musical set theory * ...
'' of a permutation ''σ'' is a pair of positions where the entries of a permutation are in the opposite order: i < j and \sigma_i > \sigma_j. So a descent is just an inversion at two adjacent positions. For example, the permutation has three inversions: (1, 3), (2, 3), and (4, 5), for the pairs of entries (2, 1), (3, 1), and (5, 4). Sometimes an inversion is defined as the pair of values whose order is reversed; this makes no difference for the ''number'' of inversions, and this pair (reversed) is also an inversion in the above sense for the inverse permutation ''σ''−1. The number of inversions is an important measure for the degree to which the entries of a permutation are out of order; it is the same for ''σ'' and for ''σ''−1. To bring a permutation with ''k'' inversions into order (that is, transform it into the identity permutation), by successively applying (right-multiplication by)
adjacent transposition In mathematics, and in particular in group theory, a cyclic permutation (or cycle) is a permutation of the elements of some set (mathematics), set ''X'' which maps the elements of some subset ''S'' of ''X'' to each other in a cyclic fashion, while ...
s, is always possible and requires a sequence of ''k'' such operations. Moreover, any reasonable choice for the adjacent transpositions will work: it suffices to choose at each step a transposition of ''i'' and where ''i'' is a descent of the permutation as modified so far (so that the transposition will remove this particular descent, although it might create other descents). This is so because applying such a transposition reduces the number of inversions by 1; as long as this number is not zero, the permutation is not the identity, so it has at least one descent.
Bubble sort Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes ...
and
insertion sort Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Howev ...
can be interpreted as particular instances of this procedure to put a sequence into order. Incidentally this procedure proves that any permutation ''σ'' can be written as a product of adjacent transpositions; for this one may simply reverse any sequence of such transpositions that transforms ''σ'' into the identity. In fact, by enumerating all sequences of adjacent transpositions that would transform ''σ'' into the identity, one obtains (after reversal) a ''complete'' list of all expressions of minimal length writing ''σ'' as a product of adjacent transpositions. The number of permutations of ''n'' with ''k'' inversions is expressed by a Mahonian number, it is the coefficient of ''X''''k'' in the expansion of the product \prod_^n\sum_^X^i = 1 \left(1 + X\right)\left(1 + X + X^2\right) \cdots \left(1 + X + X^2 + \cdots + X^\right), which is also known (with ''q'' substituted for ''X'') as the
q-factorial In mathematical area of combinatorics, the ''q''-Pochhammer symbol, also called the ''q''-shifted factorial, is the product (a;q)_n = \prod_^ (1-aq^k)=(1-a)(1-aq)(1-aq^2)\cdots(1-aq^), with (a;q)_0 = 1. It is a ''q''-analog of the Pochhammer symb ...
/nowiki>''n''/nowiki>''q''! . The expansion of the product appears in
Necklace (combinatorics) In combinatorics, a ''k''-ary necklace of length ''n'' is an equivalence class of ''n''-character strings over an alphabet of size ''k'', taking all rotations as equivalent. It represents a structure with ''n'' circularly connected beads which ...
. Let \sigma \in S_n, i, j\in \ such that i and \sigma(i)>\sigma(j). In this case, say the weight of the inversion (i, j) is \sigma(i)-\sigma(j). Kobayashi (2011) proved the enumeration formula \sum_(\sigma(i)-\sigma(j)) = , \ where \le denotes Bruhat order in the symmetric groups. This graded partial order often appears in the context of Coxeter groups.


Permutations in computing


Numbering permutations

One way to represent permutations of ''n'' things is by an integer ''N'' with 0 ≤ ''N'' < ''n''!, provided convenient methods are given to convert between the number and the representation of a permutation as an ordered arrangement (sequence). This gives the most compact representation of arbitrary permutations, and in computing is particularly attractive when ''n'' is small enough that ''N'' can be held in a machine word; for 32-bit words this means ''n'' ≤ 12, and for 64-bit words this means ''n'' ≤ 20. The conversion can be done via the intermediate form of a sequence of numbers ''d''''n'', ''d''''n''−1, ..., ''d''2, ''d''1, where ''d''''i'' is a non-negative integer less than ''i'' (one may omit ''d''1, as it is always 0, but its presence makes the subsequent conversion to a permutation easier to describe). The first step then is to simply express ''N'' in the ''
factorial number system In combinatorics, the factorial number system, also called factoradic, is a mixed radix numeral system adapted to numbering permutations. It is also called factorial base, although factorials do not function as base, but as place value of digit ...
'', which is just a particular
mixed radix Mixed radix numeral systems are non-standard positional numeral systems in which the numerical radix, base varies from position to position. Such numerical representation applies when a quantity is expressed using a sequence of units that are eac ...
representation, where, for numbers less than ''n''!, the bases (place values or multiplication factors) for successive digits are , , ..., 2!, 1!. The second step interprets this sequence as a
Lehmer code In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encoding, encode each possible permutation of a sequence of ''n'' numbers. It is an instance of a scheme for Permutation#Numbering permutations, numbering perm ...
or (almost equivalently) as an inversion table. In the Lehmer code for a permutation ''σ'', the number ''d''''n'' represents the choice made for the first term ''σ''1, the number ''d''''n''−1 represents the choice made for the second term ''σ''2 among the remaining elements of the set, and so forth. More precisely, each ''d''''n''+1−''i'' gives the number of ''remaining'' elements strictly less than the term ''σ''''i''. Since those remaining elements are bound to turn up as some later term ''σ''''j'', the digit ''d''''n''+1−''i'' counts the ''inversions'' (''i'',''j'') involving ''i'' as smaller index (the number of values ''j'' for which ''i'' < ''j'' and ''σ''''i'' > ''σ''''j''). The inversion table for ''σ'' is quite similar, but here ''d''''n''+1−''k'' counts the number of inversions (''i'',''j'') where ''k'' = ''σ''''j'' occurs as the smaller of the two values appearing in inverted order. Both encodings can be visualized by an ''n'' by ''n'' Rothe diagram (named after
Heinrich August Rothe Heinrich August Rothe (1773–1842) was a German mathematician, a professor of mathematics at Erlangen. He was a student of Carl Hindenburg and a member of Hindenburg's school of combinatorics. Biography Rothe was born in 1773 in Dresden, and in ...
) in which dots at (''i'',''σ''''i'') mark the entries of the permutation, and a cross at (''i'',''σ''''j'') marks the inversion (''i'',''j''); by the definition of inversions a cross appears in any square that comes both before the dot (''j'',''σ''''j'') in its column, and before the dot (''i'',''σ''''i'') in its row. The Lehmer code lists the numbers of crosses in successive rows, while the inversion table lists the numbers of crosses in successive columns; it is just the Lehmer code for the inverse permutation, and vice versa. To effectively convert a Lehmer code ''d''''n'', ''d''''n''−1, ..., ''d''2, ''d''1 into a permutation of an ordered set ''S'', one can start with a list of the elements of ''S'' in increasing order, and for ''i'' increasing from 1 to ''n'' set ''σ''''i'' to the element in the list that is preceded by ''d''''n''+1−''i'' other ones, and remove that element from the list. To convert an inversion table ''d''''n'', ''d''''n''−1, ..., ''d''2, ''d''1 into the corresponding permutation, one can traverse the numbers from ''d''1 to ''d''''n'' while inserting the elements of ''S'' from largest to smallest into an initially empty sequence; at the step using the number ''d'' from the inversion table, the element from ''S'' inserted into the sequence at the point where it is preceded by ''d'' elements already present. Alternatively one could process the numbers from the inversion table and the elements of ''S'' both in the opposite order, starting with a row of ''n'' empty slots, and at each step place the element from ''S'' into the empty slot that is preceded by ''d'' other empty slots. Converting successive natural numbers to the factorial number system produces those sequences in
lexicographic order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
(as is the case with any mixed radix number system), and further converting them to permutations preserves the lexicographic ordering, provided the Lehmer code interpretation is used (using inversion tables, one gets a different ordering, where one starts by comparing permutations by the ''place'' of their entries 1 rather than by the value of their first entries). The sum of the numbers in the factorial number system representation gives the number of inversions of the permutation, and the parity of that sum gives the
signature A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
of the permutation. Moreover, the positions of the zeroes in the inversion table give the values of left-to-right maxima of the permutation (in the example 6, 8, 9) while the positions of the zeroes in the Lehmer code are the positions of the right-to-left minima (in the example positions the 4, 8, 9 of the values 1, 2, 5); this allows computing the distribution of such extrema among all permutations. A permutation with Lehmer code ''d''''n'', ''d''''n''−1, ..., ''d''2, ''d''1 has an ascent if and only if .


Algorithms to generate permutations

In computing it may be required to generate permutations of a given sequence of values. The methods best adapted to do this depend on whether one wants some randomly chosen permutations, or all permutations, and in the latter case if a specific ordering is required. Another question is whether possible equality among entries in the given sequence is to be taken into account; if so, one should only generate distinct multiset permutations of the sequence. An obvious way to generate permutations of ''n'' is to generate values for the
Lehmer code In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encoding, encode each possible permutation of a sequence of ''n'' numbers. It is an instance of a scheme for Permutation#Numbering permutations, numbering perm ...
(possibly using the
factorial number system In combinatorics, the factorial number system, also called factoradic, is a mixed radix numeral system adapted to numbering permutations. It is also called factorial base, although factorials do not function as base, but as place value of digit ...
representation of integers up to ''n''!), and convert those into the corresponding permutations. However, the latter step, while straightforward, is hard to implement efficiently, because it requires ''n'' operations each of selection from a sequence and deletion from it, at an arbitrary position; of the obvious representations of the sequence as an
array An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
or a
linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
, both require (for different reasons) about ''n''2/4 operations to perform the conversion. With ''n'' likely to be rather small (especially if generation of all permutations is needed) that is not too much of a problem, but it turns out that both for random and for systematic generation there are simple alternatives that do considerably better. For this reason it does not seem useful, although certainly possible, to employ a special data structure that would allow performing the conversion from Lehmer code to permutation in ''O''(''n'' log ''n'') time.


Random generation of permutations

For generating
random permutation A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and sim ...
s of a given sequence of ''n'' values, it makes no difference whether one applies a randomly selected permutation of ''n'' to the sequence, or chooses a random element from the set of distinct (multiset) permutations of the sequence. This is because, even though in case of repeated values there can be many distinct permutations of ''n'' that result in the same permuted sequence, the number of such permutations is the same for each possible result. Unlike for systematic generation, which becomes unfeasible for large ''n'' due to the growth of the number ''n''!, there is no reason to assume that ''n'' will be small for random generation. The basic idea to generate a random permutation is to generate at random one of the ''n''! sequences of integers ''d''1,''d''2,...,''d''''n'' satisfying (since ''d''1 is always zero it may be omitted) and to convert it to a permutation through a
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
correspondence. For the latter correspondence one could interpret the (reverse) sequence as a Lehmer code, and this gives a generation method first published in 1938 by
Ronald Fisher Sir Ronald Aylmer Fisher (17 February 1890 – 29 July 1962) was a British polymath who was active as a mathematician, statistician, biologist, geneticist, and academic. For his work in statistics, he has been described as "a genius who a ...
and
Frank Yates Frank Yates FRS (12 May 1902 – 17 June 1994) was one of the pioneers of 20th-century statistics. Biography Yates was born in Manchester, England, the eldest of five children (and only son) of seed merchant Percy Yates and his wife Edith. H ...
. While at the time computer implementation was not an issue, this method suffers from the difficulty sketched above to convert from Lehmer code to permutation efficiently. This can be remedied by using a different bijective correspondence: after using ''d''''i'' to select an element among ''i'' remaining elements of the sequence (for decreasing values of ''i''), rather than removing the element and compacting the sequence by shifting down further elements one place, one swaps the element with the final remaining element. Thus the elements remaining for selection form a consecutive range at each point in time, even though they may not occur in the same order as they did in the original sequence. The mapping from sequence of integers to permutations is somewhat complicated, but it can be seen to produce each permutation in exactly one way, by an immediate
induction Induction, Inducible or Inductive may refer to: Biology and medicine * Labor induction (birth/pregnancy) * Induction chemotherapy, in medicine * Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
. When the selected element happens to be the final remaining element, the swap operation can be omitted. This does not occur sufficiently often to warrant testing for the condition, but the final element must be included among the candidates of the selection, to guarantee that all permutations can be generated. The resulting algorithm for generating a random permutation of ''a'' ''a'' ..., ''a'' 'n'' − 1/code> can be described as follows in
pseudocode In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
: for ''i'' from ''n'' downto 2 do ''di'' ← random element of swap ''a'' 'di''and ''a'' 'i'' − 1 This can be combined with the initialization of the array ''a'' 'i''= ''i'' as follows for ''i'' from 0 to ''n''−1 do ''d''''i''+1 ← random element of ''a'' 'i''← ''a'' 'd''''i''+1 ''a'' 'd''''i''+1← ''i'' If ''d''''i''+1 = ''i'', the first assignment will copy an uninitialized value, but the second will overwrite it with the correct value ''i''. However, Fisher-Yates is not the fastest algorithm for generating a permutation, because Fisher-Yates is essentially a sequential algorithm and "divide and conquer" procedures can achieve the same result in parallel.


Generation in lexicographic order

There are many ways to systematically generate all permutations of a given sequence. One classic, simple, and flexible algorithm is based upon finding the next permutation in
lexicographic ordering In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of ...
, if it exists. It can handle repeated values, for which case it generates each distinct multiset permutation once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the
factorial number system In combinatorics, the factorial number system, also called factoradic, is a mixed radix numeral system adapted to numbering permutations. It is also called factorial base, although factorials do not function as base, but as place value of digit ...
) and converting those to permutations. It begins by sorting the sequence in (weakly)
increasing In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. The method goes back to
Narayana Pandit Nārāyaṇa Paṇḍita ( sa, नारायण पण्डित) (1340–1400) was an Indian mathematician. Plofker writes that his texts were the most significant Sanskrit mathematics treatises after those of Bhaskara II, other than the K ...
a in 14th century India, and has been rediscovered frequently. The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place. # Find the largest index ''k'' such that . If no such index exists, the permutation is the last permutation. # Find the largest index ''l'' greater than ''k'' such that . # Swap the value of ''a'' 'k''with that of ''a'' 'l'' # Reverse the sequence from ''a'' 'k'' + 1up to and including the final element ''a'' 'n'' For example, given the sequence
, 2, 3, 4 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
(which is in increasing order), and given that the index is zero-based, the steps are as follows: # Index ''k'' = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than ''a'' 'k'' + 1which is 4. # Index ''l'' = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition ''a'' 'k''< ''a'' 'l'' # The values of ''a'' and ''a'' are swapped to form the new sequence
, 2, 4, 3 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
# The sequence after ''k''-index ''a'' to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted:
, 2, 4, 3 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
Following this algorithm, the next lexicographic permutation will be
, 3, 2, 4 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
and the 24th permutation will be
, 3, 2, 1 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
at which point ''a'' 'k''< ''a'' 'k'' + 1does not exist, indicating that this is the last permutation. This method uses about 3 comparisons and 1.5 swaps per permutation, amortized over the whole sequence, not counting the initial sort.


Generation with minimal changes

An alternative to the above algorithm, the
Steinhaus–Johnson–Trotter algorithm The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of n elements. E ...
, generates an ordering on all the permutations of a given sequence with the property that any two consecutive permutations in its output differ by swapping two adjacent values. This ordering on the permutations was known to 17th-century English bell ringers, among whom it was known as "plain changes". One advantage of this method is that the small amount of change from one permutation to the next allows the method to be implemented in constant time per permutation. The same can also easily generate the subset of even permutations, again in constant time per permutation, by skipping every other output permutation. An alternative to Steinhaus–Johnson–Trotter is
Heap's algorithm Heap's algorithm generates all possible permutations of objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; th ...
, said by Robert Sedgewick in 1977 to be the fastest algorithm of generating permutations in applications. The following figure shows the output of all three aforementioned algorithms for generating all permutations of length n=4, and of six additional algorithms described in the literature. # Lexicographic ordering; #
Steinhaus–Johnson–Trotter algorithm The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of n elements. E ...
; #
Heap's algorithm Heap's algorithm generates all possible permutations of objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; th ...
; # Ehrlich's star-transposition algorithm: in each step, the first entry of the permutation is exchanged with a later entry; # Zaks' prefix reversal algorithm: in each step, a prefix of the current permutation is reversed to obtain the next permutation; # Sawada-Williams' algorithm: each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries; # Corbett's algorithm: each permutation differs from the previous one by a cyclic left-shift of some prefix by one position; # Single-track ordering: each column is a cyclic shift of the other columns; # Single-track Gray code: each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions.


Meandric permutations

Meandric systems give rise to ''meandric permutations'', a special subset of ''alternate permutations''. An alternate permutation of the set is a
cyclic permutation In mathematics, and in particular in group theory, a cyclic permutation (or cycle) is a permutation of the elements of some set ''X'' which maps the elements of some subset ''S'' of ''X'' to each other in a cyclic fashion, while fixing (that is, ma ...
(with no fixed points) such that the digits in the cyclic notation form alternate between odd and even integers. Meandric permutations are useful in the analysis of RNA secondary structure. Not all alternate permutations are meandric. A modification of Heap's algorithm has been used to generate all alternate permutations of order ''n'' (that is, of length 2''n'') without generating all (2''n'')! permutations. Generation of these alternate permutations is needed before they are analyzed to determine if they are meandric or not. The algorithm is recursive. The following table exhibits a step in the procedure. In the previous step, all alternate permutations of length 5 have been generated. Three copies of each of these have a "6" added to the right end, and then a different transposition involving this last entry and a previous entry in an even position is applied (including the identity; that is, no transposition).


Applications

Permutations are used in the
interleaver In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
component of the
error detection and correction In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communi ...
algorithms, such as
turbo codes In information theory, turbo codes (originally in French ''Turbocodes'') are a class of high-performance forward error correction (FEC) codes developed around 1990–91, but first published in 1993. They were the first practical codes to closely ...
, for example
3GPP Long Term Evolution In telecommunications, long-term evolution (LTE) is a standard for wireless broadband communication for mobile devices and data terminals, based on the GSM/EDGE and UMTS/HSPA standards. It improves on those standards' capacity and speed by usi ...
mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212). Such applications raise the question of fast generation of permutations satisfying certain desirable properties. One of the methods is based on the
permutation polynomials In mathematics, a permutation polynomial (for a given ring) is a polynomial that acts as a permutation of the elements of the ring, i.e. the map x \mapsto g(x) is a bijection. In case the ring is a finite field, the Dickson polynomials, which are ...
. Also as a base for optimal hashing in Unique Permutation Hashing.


See also

*
Alternating permutation In combinatorial mathematics, an alternating permutation (or zigzag permutation) of the set is a permutation (arrangement) of those numbers so that each entry is alternately greater or less than the preceding entry. For example, the five alte ...
*
Convolution In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions ( and ) that produces a third function (f*g) that expresses how the shape of one is ...
*
Cyclic order In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. In ...
*
Even and odd permutations In mathematics, when ''X'' is a finite set with at least two elements, the permutations of ''X'' (i.e. the bijective functions from ''X'' to ''X'') fall into two classes of equal size: the even permutations and the odd permutations. If any total or ...
*
Josephus permutation In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. A number of people are standing in a circle waiting to be executed. Counting begins at a specif ...
*
Levi-Civita symbol In mathematics, particularly in linear algebra, tensor analysis, and differential geometry, the Levi-Civita symbol or Levi-Civita epsilon represents a collection of numbers; defined from the sign of a permutation of the natural numbers , for some ...
*
List of permutation topics This is a list of topics on mathematical permutations. Particular kinds of permutations *Alternating permutation *Circular shift *Cyclic permutation *Derangement *Even and odd permutations—see Parity of a permutation *Josephus permutation ...
*
Major index In mathematics (and particularly in combinatorics), the major index of a permutation is the sum of the positions of the descents of the permutation. In symbols, the major index of the permutation ''w'' is : \operatorname(w) = \sum_ i. For e ...
*
Permutation category In mathematics, the permutation category is a category where #the objects are the natural numbers, #the morphisms from a natural number ''n'' to itself are the elements of the symmetric group In abstract algebra, the symmetric group defined o ...
*
Permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...
*
Permutation pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the pe ...
*
Permutation representation (symmetric group) In mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from sym ...
*
Probability Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
*
Rencontres numbers In combinatorial mathematics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set with specified numbers of fixed points: in other words, partial derangements. (''Rencontre'' is French for ''encounter' ...
*
Sorting network In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such net ...
*
Substitution cipher In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters (the most common), pairs of letters, trip ...
*
Superpattern In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a ''k''-superpattern contains all possible patterns ...
*
Superpermutation In combinatorial mathematics, a superpermutation on ''n'' symbols is a string that contains each permutation of ''n'' symbols as a substring. While trivial superpermutations can simply be made up of every permutation listed together, superpermuta ...
*
Twelvefold way In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a ...
*
Weak order of permutations In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order. Definitions Inversion Let \pi be a permutation. There is an inversion of \pi between i and j if i \pi(j). ...


Notes


References


Bibliography

* * * * * * * * * * * This book mentions the Lehmer code (without using that name) as a variant ''C''1,...,''C''''n'' of inversion tables in exercise 5.1.1–7 (p. 19), together with two other variants. * Fascicle 2, first printing. * * * * The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed. ''In quotations the original long "S" has been replaced by a modern short "s".'' *


Further reading

* * . The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag. * . Section 5.1: Combinatorial Properties of Permutations, pp. 11–72. * *


External links

* {{Commons category, Permutations Arab inventions