View source for Permutation

{{Short description|Mathematical version of an order change}}
{{Other uses}}
{{redirect|nPr||NPR (disambiguation)}}
<!-- {{In use}}  Back later! --> 
[[File:Permutations RGB.svg|thumb|120 px|According to the first meaning of permutation, each of the six rows is a different permutation of three distinct balls]]
In [[mathematics]], a '''permutation''' of a [[Set (mathematics)|set]] can mean one of two different things:
* an arrangement of its members in a [[sequence]] or [[linear order]], or
* the act or process of changing the linear order of an ordered set.<ref>{{harvtxt|Webster|1969}}</ref>

An example of the first meaning is the six permutations (orderings) of the set {1, 2, 3}: written as [[tuple]]s, they are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). [[Anagram]]s of a word whose letters are all different are also permutations: the letters are already ordered in the original word, and the anagram reorders them. The study of permutations of [[finite set]]s is an important topic in [[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]] sequences.

{{anchor|n-factorial}}The number of permutations of {{math|''n''}} distinct objects is {{math|''n''}}&nbsp;[[factorial]], usually written as {{math|''n''!}}, which means the product of all positive integers less than or equal to {{math|''n''}}.

According to the second meaning, a permutation of a [[Set (mathematics)|set]] {{math|''S''}} is defined as a [[bijection]] from {{math|''S''}} to itself.<ref>{{harvtxt|McCoy|1968|p=152}}</ref><ref>{{harvtxt|Nering|1970|p=86}}</ref> That is, it is a [[function (mathematics)|function]] from {{math|''S''}} to {{math|''S''}} for which every element occurs exactly once as an [[image (mathematics)|image]] value. Such a function <math>\sigma : S \to S</math> is equivalent to the rearrangement of the elements of {{math|''S''}} in which each element ''i'' is replaced by the corresponding <math>\sigma(i)</math>. For example, the permutation (3, 1, 2) is described by the function <math>\sigma</math> defined as

: <math>\sigma(1) = 3, \quad \sigma(2) = 1, \quad \sigma(3) = 2</math>.

The collection of all permutations of a set form a [[group (mathematics)|group]] called the [[symmetric group]] of the set. The group operation is the [[function composition|composition]] of functions (performing one rearrangement after the other), which results in another function (rearrangement). The properties of permutations do not depend on the nature of the elements being permuted, only on their number, so one often considers the standard set <math>S=\{1, 2, \ldots, n\}</math>.

In elementary combinatorics, the '''{{math|''k''}}-permutations''', or [[partial permutation]]s, are the ordered arrangements of {{math|''k''}} distinct elements selected from a set. When {{math|''k''}} is equal to the size of the set, these are the permutations in the previous sense.

[[Image:Rubik's cube.svg|thumb|In the popular puzzle [[Rubik's cube]] invented in 1974 by [[Ernő Rubik]], each turn of the puzzle faces creates a permutation of the surface colors.]]

==History==
Permutation-like objects called [[Hexagram (I Ching)|hexagrams]] were used in China in the [[I Ching]] ([[Pinyin]]: Yi Jing) as early as 1000 BC.

In Greece, [[Plutarch]] wrote that [[Xenocrates]] of Chalcedon (396–314 BC) discovered the number of different syllables possible in the Greek language. This would have been the first attempt on record to solve a difficult problem in permutations and combinations.<ref>{{Cite book |last=Heath |first=Thomas Little |url=https://www.worldcat.org/oclc/7703465 |title=A History of Greek Mathematics |date=1981 |publisher=Dover Publications |isbn=0-486-24073-8 |location=New York |oclc=7703465}}</ref>

[[Al-Khalil ibn Ahmad al-Farahidi|Al-Khalil]] (717–786), an [[Mathematics in medieval Islam|Arab mathematician]] and [[cryptographer]], wrote the ''Book of Cryptographic Messages''. It contains the first use of permutations and combinations, to list all possible [[Arabic language|Arabic]] words with and without vowels.<ref name="LB">{{cite journal|last=Broemeling|first=Lyle D.|title=An Account of Early Statistical Inference in Arab Cryptology|journal=The American Statistician|date=1 November 2011|volume=65|issue=4|pages=255–257|doi=10.1198/tas.2011.10191|s2cid=123537702}}</ref>

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 [[Bhāskara II]] contains a passage that translates as follows:
<blockquote>
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.<ref>{{cite journal |first=N. L. |last=Biggs |title=The Roots of Combinatorics |journal=Historia Math. |volume=6 |year=1979 |issue=2 |pages=109–136 |doi=10.1016/0315-0860(79)90074-0 |doi-access= }}</ref>
</blockquote>

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.{{sfn|Stedman|1677|p=4}}  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".{{sfn|Stedman|1677|p=5}}  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.{{sfn|Stedman|1677|pp=6—7}}  At this point he gives up and remarks:
<blockquote>
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;{{sfn|Stedman|1677|p=8}}
</blockquote>
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.{{sfn|Stedman|1677|pp=13—18}}

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 [[Polynomial#Solving polynomial equations|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 played an important role in the [[Cryptanalysis of the Enigma|cryptanalysis of the Enigma machine]], a cipher device used by [[Nazi Germany]] during [[World War II]]. In particular, one important property of permutations, namely, that two permutations are conjugate exactly when they have the same cycle type, was used by cryptologist [[Marian Rejewski]] to break the German Enigma cipher in turn of years 1932-1933.<ref>{{Cite journal |last=Rejewski |first=Marian |date=1980 |title=An application of the theory of permutations in breaking the Enigma cipher |url=https://eudml.org/doc/264403 |journal=Applicationes Mathematicae |volume=16 |issue=4 |pages=543–559 |doi=10.4064/am-16-4-543-559 |issn=1233-7234|doi-access=free }}</ref><ref>{{Cite web |last=Cash |first=David |date=2019 |title=CMSC 28400 Introduction to Cryptography Autumn 2019 - Notes #2: Permutations and Enigma |url=https://people.cs.uchicago.edu/~davidcash/284-autumn-19/02-permutations-and-enigma.pdf}}</ref>

==Definition==

In mathematics texts it is customary to denote permutations using lowercase Greek letters. Commonly, either <math>\alpha,\beta,\gamma</math> or <math>\sigma, \tau,\rho,\pi</math> are used.<ref name="Scheinerman">{{cite book |last1=Scheinerman |first1=Edward A. |date=March 5, 2012 |chapter=Chapter 5: Functions |title=Mathematics: A Discrete Introduction |chapter-url=https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA188 |url-status=live |edition=3rd |publisher=Cengage Learning |page=188 |isbn=978-0840049421 |archive-url=https://web.archive.org/web/20200205212843/https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA188 |archive-date=February 5, 2020 |access-date=February 5, 2020 |quote=It is customary to use lowercase Greek letters (especially π, σ, and τ) to stand for permutations.}}</ref>

A permutation can be defined as a [[bijection]] (an invertible mapping, a one-to-one and onto function) from a set {{math|''S''}} to itself: <blockquote><math>\sigma : S\ \stackrel{\sim}{\longrightarrow}\ S.</math> </blockquote>The [[identity permutation]] is defined by <math>\sigma(x) = x  </math> for all elements <math>x\in S  </math>, and can be denoted by the number <math>1</math>,{{efn|1 is frequently used to represent the [[identity element]] in a non-commutative group}} by <math>\text{id}= \text{id}_S   </math>, or by a single 1-cycle (x).<ref>{{harvnb|Rotman|2002|p=41}}</ref><ref>{{harvnb|Bogart|1990|p=487}}</ref>

The set of all permutations of a set with ''n'' elements forms the [[symmetric group]] <math>S_n</math>, where the [[group operation]] is [[composition of functions]]. Thus for two permutations <math>\sigma</math> and <math>\tau</math> in the group <math>S_n</math>, their product <math>\pi = \sigma\tau</math> is defined by: <blockquote><math>\pi(i)=\sigma(\tau(i)).</math> </blockquote>Composition is usually written without a dot or other sign. In general, composition of two permutations is not [[commutative]]: <math>\tau\sigma \neq \sigma\tau.</math>

As a bijection from a set to itself, a permutation is a function that ''performs'' a rearrangement of a set, termed an ''active permutation'' or ''substitution''. An older viewpoint sees a permutation as an ordered arrangement or list of all the elements of ''S'', called a ''passive permutation''.{{sfn|Cameron|1994|loc=p. 29, footnote 3}} According to this definition, all permutations in {{Section link||One-line notation}} are passive. This meaning is subtly distinct from how passive (i.e. ''alias'') is used in [[Active and passive transformation]] and elsewhere,<ref>{{cite book |last1=Conway |first1=John H. |last2=Burgiel |first2=Heidi |last3=Goodman-Strauss |first3=Chaim |date=2008 |title=The Symmetries of Things |publisher=A K Peters |page=179 |quote=A permutation---say, of the names of a number of people---can be thought of as moving either the names or the people.  The alias viewpoint regards the permutation as assigning a new name or ''alias'' to each person (from the Latin ''alias'' = otherwise).  Alternatively, from the alibi viewoint we move the people to the places corresponding to their new names (from the Latin ''alibi'' = in another place.) }}</ref><ref>{{Cite web |title=Permutation notation - Wikiversity |url=https://en.wikiversity.org/wiki/Permutation_notation |access-date=2024-08-04 |website=en.wikiversity.org |language=en}}</ref> which would consider all permutations open to passive interpretation (regardless of whether they are in one-line notation, two-line notation, etc.).

A permutation <math>\sigma</math> can be decomposed into one or more disjoint ''cycles'' which are the [[Orbit (group theory)|orbits]] of the cyclic group <math>\langle\sigma\rangle = \{1, \sigma, \sigma^2,\ldots\} </math> [[Group action|acting]] on the set ''S''. A cycle is found by repeatedly applying the permutation to an element: <math>x, \sigma(x),\sigma(\sigma(x)),\ldots, \sigma^{k-1}(x)</math>, where we assume <math>\sigma^k(x)=x</math> . A cycle consisting of ''k'' elements is called a ''k''-cycle. (See {{Section link||Cycle notation}} below.)

A [[Fixed point (mathematics)|fixed point]] of a permutation <math>\sigma</math> is an element ''x'' which is taken to itself, that is <math>\sigma(x)=x </math>, forming a 1-cycle <math>(\,x\,)</math>. A permutation with no fixed points is called a [[derangement]]. A permutation exchanging two elements (a single 2-cycle) and leaving the others fixed is called a [[transposition (mathematics)|transposition]].

==Notations==
{{anchor|Two-line notation}} Several notations are widely used to represent permutations conveniently. ''Cycle notation'' is a popular choice, as it is compact and shows the permutation's structure clearly. This article will use cycle notation unless otherwise specified.

===Two-line notation===
[[Augustin-Louis Cauchy|Cauchy]]'s ''two-line notation''<ref>{{cite journal |last1=Cauchy |first1=A. L. |title=Mémoire Sur le Nombre des Valeurs qu'une Fonction peut acquérir, lorsqu'on y permute de toutes les manières possibles les quantités qu'elle renferme |journal=Journal de l'École polytechnique |date=January 1815 |volume=10 |pages=1–28 |url=https://babel.hathitrust.org/cgi/pt?id=mdp.39015074785612&seq=9 |trans-title=Memoir on the number of values which a function can acquire when one permutes within it, in all possible ways, the variables which it contains |language=French}}  See p. 4.
* [https://nonagon.org/ExLibris/cauchys-memoire-sur-le-nombre-des-valeurs English translation]</ref><ref>{{citation|title=The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory|first=Hans|last=Wussing|publisher=Courier Dover Publications|year=2007|isbn=9780486458687|page=94|url=https://books.google.com/books?id=Xp3JymnfAq4C&pg=PA94|quote=Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.}}</ref> lists the elements of ''S'' in the first row, and the image of each element below it in the second row. For example, the permutation of ''S'' = {1, 2, 3, 4, 5, 6} given by the function<blockquote><math>\sigma(1) = 2, \ \ \sigma(2) = 6, \ \ \sigma(3) = 5, \ \ \sigma(4) = 4, \ \ \sigma(5) = 3, \ \ \sigma(6) = 1   </math></blockquote>can be written as
: <math>\sigma = \begin{pmatrix}
  1 & 2 & 3 & 4 & 5 & 6 \\
  2 & 6 & 5 & 4 & 3 & 1
\end{pmatrix}.</math>
The elements of ''S'' may appear in any order in the first row, so this permutation could also be written:
: <math>\sigma = \begin{pmatrix}
  2 & 3 & 4 & 5 & 6 & 1 \\
  6 & 5 & 4 & 3 & 1 & 2
\end{pmatrix}
= \begin{pmatrix}
  6 & 5 & 4 & 3 & 2 & 1 \\
  1 & 3 & 4 & 5 & 6 & 2 
\end{pmatrix}.</math>

===One-line notation===
If there is a "natural" order for the elements of ''S'',{{efn|The order is often implicitly understood. A set of integers is naturally written from smallest to largest; a set of letters is written in lexicographic order. For other sets, a natural order needs to be specified explicitly.}} say <math>x_1, x_2, \ldots, x_n</math>, then one uses this for the first row of the two-line notation:
: <math>\sigma = \begin{pmatrix}
  x_1         & x_2         & x_3         & \cdots & x_n \\
  \sigma(x_1) & \sigma(x_2) & \sigma(x_3) & \cdots & \sigma(x_n)
\end{pmatrix}.</math>

Under this assumption, one may omit the first row and write the permutation in ''one-line notation'' as
: <math>\sigma = \sigma(x_1) \; \sigma(x_2) \; \sigma(x_3) \; \cdots \; \sigma(x_n) </math>,
that is, as an ordered arrangement of the elements of ''S''.<ref>{{harvnb|Bogart|1990|p=17}}</ref><ref>{{harvnb|Gerstein|1987|p=217}}</ref> Care must be taken to distinguish one-line notation from the cycle notation described below: a common usage is to omit parentheses or other enclosing marks for one-line notation, while using parentheses for cycle notation. The one-line notation is also called the ''[[Word (mathematics)|word]] representation''.<ref name="Aigner2007"/>

The example above would then be:<blockquote><math>\sigma = \begin{pmatrix}
  1 & 2 & 3 & 4 & 5 & 6 \\
  2 & 6 & 5 & 4 & 3 & 1
\end{pmatrix} 
= 2  6  5  4  3  1.</math> </blockquote>(It is typical to use commas to separate these entries only if some have two or more digits.)

This compact form is common in elementary [[combinatorics]] and [[computer science]]. It is especially useful in applications where the permutations are to be compared as [[Partially ordered set|larger or smaller]] using [[lexicographic order]].

===Cycle notation===
Cycle notation describes the effect of repeatedly applying the permutation on the elements of the set ''S'', with an orbit being called a ''cycle''. The permutation is written as a list of cycles; since distinct cycles involve [[disjoint sets|disjoint]] sets of elements, this is referred to as "decomposition into disjoint cycles".

To write down the permutation <math>\sigma</math> in cycle notation, one proceeds as follows:

# Write an opening bracket followed by an arbitrary element ''x'' of <math>S</math>:  <math>(\,x</math>
# Trace the orbit of ''x'', writing down the values under successive applications of <math>\sigma</math>: <math>(\,x,\sigma(x),\sigma(\sigma(x)),\ldots</math>
# Repeat until the value returns to ''x,'' and close the parenthesis without repeating ''x'': <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)</math>
# Continue with an element ''y'' of ''S'' which was not yet written, and repeat the above process: <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)(\,y\,\ldots\,)</math>
# Repeat until all elements of ''S'' are written in cycles.

Also, it is common to omit 1-cycles, since these can be inferred: for any element ''x'' in ''S'' not appearing in any cycle, one implicitly assumes <math>\sigma(x) = x</math>.<ref>{{harvnb|Hall|1959|p=54}}</ref>

Following the convention of omitting 1-cycles, one may interpret an individual cycle as a permutation which fixes all the elements not in the cycle (a [[cyclic permutation]] having only one cycle of length greater than 1). Then the list of disjoint cycles can be seen as the composition of these cyclic permutations. For example, the one-line permutation <math>\sigma = 2 6 5 4 3 1  </math> can be written in cycle notation as:<blockquote><math>\sigma = (126)(35)(4) = (126)(35).  </math></blockquote>This may be seen as the composition <math>\sigma = \kappa_1 \kappa_2  </math> of cyclic permutations:<blockquote><math>\kappa_1 = (126) = (126)(3)(4)(5),\quad \kappa_2 = (35)= (35)(1)(2)(6).  </math> </blockquote>While permutations in general do not commute, disjoint cycles do; for example:<blockquote><math>\sigma = (126)(35) = (35)(126).  </math></blockquote>Also, each cycle can be rewritten from a different starting point; for example,<blockquote><math>\sigma = (126)(35) = (261)(53).  </math></blockquote>Thus one may write the disjoint cycles of a given permutation in many different ways.

A convenient feature of cycle notation is that inverting the permutation is given by reversing the order of the elements in each cycle. For example, <blockquote><math>\sigma^{-1} = \left(\vphantom{A^2}(126)(35)\right)^{-1} = (621)(53).  </math></blockquote>

=== 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]] 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, not omitting 1-cycles

For example, <blockquote>(513)(6)(827)(94) </blockquote>is a permutation of ''S ='' {1, 2, . . . , 9} in canonical cycle notation.<ref>{{harvnb|Bona|2012|loc=p.87}} [The book has a typo/error here, as it gives (45) instead of (54).]</ref>

[[Richard P. Stanley|Richard Stanley]] calls this the "standard representation" of a permutation,<ref name="Stanley2012">{{cite book |last=Stanley |first=Richard P. |title=Enumerative Combinatorics: Volume I, Second Edition |publisher=Cambridge University Press |year=2012 |isbn=978-1-107-01542-5 |page=30, Prop 1.3.1}}</ref> and Martin Aigner uses "standard form".<ref name="Aigner2007">{{cite book|first=Martin|last= Aigner|title=A Course in Enumeration|url=https://archive.org/details/courseenumeratio00aign_007|url-access=limited|year=2007|publisher=Springer GTM 238|isbn=978-3-540-39035-0|pages=[https://archive.org/details/courseenumeratio00aign_007/page/n32 24]–25}}</ref> [[Sergey Kitaev]] also uses the "standard form" terminology, but reverses both choices; that is, each cycle lists its minimal element first, and the cycles are sorted in decreasing order of their minimal elements.<ref name="Kitaev2011">{{cite book|first=Sergey |last=Kitaev|title=Patterns in Permutations and Words|year=2011|publisher=Springer Science & Business Media|isbn=978-3-642-17333-2|page=119}}</ref>

===Composition of permutations===
There are two ways to denote the composition of two permutations. In the most common notation, <math>\sigma\cdot \tau</math> is the function that maps any element ''x'' to <math>\sigma(\tau(x))</math>. The rightmost permutation is applied to the argument first,<ref>
{{cite book | last1=Biggs | first1=Norman L. | last2=White | first2=A. T.
|year=1979
|publisher=Cambridge University Press
|title=Permutation groups and combinatorial structures
|isbn=978-0-521-22287-7
}}
</ref>
because the argument is written to the right of the function.

A ''different'' rule for multiplying permutations comes from writing the argument to the left of the function, so that the leftmost permutation acts first.<ref>
{{cite book |last1=Dixon |first1=John D. |url=https://archive.org/details/permutationgroup0000dixo |title=Permutation Groups |last2=Mortimer |first2=Brian |publisher=Springer |year=1996 |isbn=978-0-387-94599-6 |url-access=registration}}
</ref><ref>
{{cite book |last1=Cameron |first1=Peter J. |url=https://archive.org/details/permutationgroup0000came |title=Permutation groups |publisher=Cambridge University Press |year=1999 |isbn=978-0-521-65302-2 |url-access=registration}}
</ref><ref>
{{cite journal |last1=Jerrum |first1=M. |year=1986 |title=A compact representation of permutation groups |journal=J. Algorithms |volume=7 |pages=60–78 |doi=10.1016/0196-6774(86)90038-6 |s2cid=18896625 |number=1}}
</ref>
In this notation, the permutation is often written as an exponent, so ''σ'' acting on ''x'' is written ''x''<sup>''σ''</sup>; then the product is defined by <math>x^{\sigma\cdot\tau} = (x^\sigma)^\tau</math>. This article uses the first definition, where the rightmost permutation is applied first.

The [[function composition]] operation satisfies the axioms of a [[Group (mathematics)|group]]. It is [[Associative property|associative]], meaning <math>(\rho\sigma)\tau = \rho(\sigma\tau)</math>, and products of more than two permutations are usually written without parentheses. The composition operation also has an identity element (the identity permutation <math>\text{id}</math>), and each permutation <math>\sigma</math> has an inverse <math>\sigma^{-1}</math> (its [[inverse function]]) with <math>\sigma^{-1}\sigma = \sigma\sigma^{-1}=\text{id}</math>.

==Other uses of the term ''permutation''==
The concept of a permutation as an ordered arrangement admits several generalizations that have been called ''permutations'', especially in older literature.

===''k''-permutations of ''n''===
In older literature and elementary textbooks, a '''''k''-permutation of ''n''''' (sometimes called a '''[[Partial permutation#Restricted partial permutations|partial permutation]]''', '''sequence without repetition''', '''variation''', or '''arrangement''') means an ordered arrangement (list) of a ''k''-element subset of an ''n''-set.{{efn|More precisely, ''variations without repetition''. The term is still common in other languages and appears in modern English most often in translation.}}<ref>{{Cite web |title=Combinations and Permutations |url=https://www.mathsisfun.com/combinatorics/combinations-permutations.html |access-date=2020-09-10 |website=www.mathsisfun.com}}</ref><ref>{{Cite web |last=Weisstein |first=Eric W. |title=Permutation |url=https://mathworld.wolfram.com/Permutation.html |access-date=2020-09-10 |website=mathworld.wolfram.com |language=en}}</ref> The number of such ''k''-permutations (''k''-arrangements) of <math>n</math> is denoted variously by such symbols as <math>P^n_k</math>,  <math>_nP_k</math>, <math>^n\!P_k</math>, <math>P_{n,k}</math>, <math>P(n,k)</math>, or <math>A^k_n</math>,<ref>{{harvnb|Uspensky|1937|p=18}}</ref> computed by the formula:<ref>{{cite book|author=Charalambides, Ch A.|title=Enumerative Combinatorics|publisher=CRC Press|year=2002|isbn=978-1-58488-290-9|page=42|url=https://books.google.com/books?id=PDMGA-v5G54C&pg=PA42}}</ref>
: <math>P(n,k) = \underbrace{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}_{k\ \mathrm{factors}}</math>,

which is 0 when {{math|''k'' &gt; ''n''}}, and otherwise is equal to
: <math>\frac{n!}{(n-k)!}.</math>

The product is well defined without the assumption that <math>n</math> is a non-negative integer, and is of importance outside combinatorics as well; it is known as the [[Pochhammer symbol]] <math>(n)_k</math> or as the <math>k</math>-th falling factorial power <math>n^{\underline k}</math>:<blockquote><math>P(n,k)={_n} P_k =(n)_k = n^{\underline{k}} .</math></blockquote>This usage of the term ''permutation'' is closely associated with the term ''[[combination]]'' to mean a subset. A ''k-combination'' of a set ''S'' is a ''k-''element subset of ''S'': the elements of a combination are not ordered. Ordering the ''k''-combinations of ''S'' in all possible ways produces 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:
: <math>C(n,k) = \frac{P(n,k)}{P(k,k)}= \frac{n^{\underline{k}}}{k!} =  \frac{n!}{(n-k)!\,k!}.</math>

These numbers are also known as [[binomial coefficient]]s, usually denoted <math>\tbinom{n}{k}</math>:<blockquote><math>C(n,k)={_n} C_k =\binom{n}{k} .</math></blockquote>

===Permutations with repetition===
Ordered arrangements of ''k'' elements of a set ''S'', where repetition is allowed, are called [[Tuple|''k''-tuples]].  They have sometimes been referred to as '''permutations with repetition''', although they are not permutations in the usual sense. They are also called [[word (mathematics)|words]] or [[String (computer science)|strings]] over the alphabet ''S''. If the set ''S'' has ''n'' elements, the number of ''k''-tuples over ''S'' is <math>n^k.</math>

===Permutations of multisets===
[[File:Permutations with repetition cropped.svg|thumb|Permutations without repetition on the left, with repetition to their right]]

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.{{efn|The natural order in this example is the order of the letters in the original word.}} If the multiplicities of the elements of ''M'' (taken in some order) are <math>m_1</math>, <math>m_2</math>, ..., <math>m_l</math> 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#Multinomial coefficients|multinomial coefficient]],<ref>{{harvnb|Brualdi|2010|loc=p. 46, Theorem 2.4.2}}</ref>
:<math>
  {n \choose m_1, m_2, \ldots, m_l} =
  \frac{n!}{m_1!\, m_2!\, \cdots\, m_l!} =
  \frac{\left(\sum_{i=1}^l{m_i}\right)!}{\prod_{i=1}^l{m_i!}}.
</math>

For example, the number of distinct anagrams of the word MISSISSIPPI is:<ref>{{harvnb|Brualdi|2010|p=47}}</ref>
:<math>\frac{11!}{1!\, 4!\, 4!\, 2!} = 34650</math>.

A '''''k''-permutation''' of a multiset ''M'' is a sequence of ''k'' 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===
{{see also|Cyclic order#Finite cycles}}
Permutations, when considered as arrangements, are sometimes referred to as ''linearly ordered'' arrangements. If, however, the objects are arranged in a circular manner this distinguished ordering is weakened: there is no "first element" in the arrangement, as any element can be considered as the start. An arrangement of distinct objects in a circular manner is called a '''circular permutation'''.<ref>{{harvnb|Brualdi|2010|p=39}}</ref>{{efn|In older texts ''circular permutation'' was sometimes used as a synonym for [[cyclic permutation]], but this is no longer done. See {{harvtxt|Carmichael|1956|p=7}}}} These can be formally defined as [[equivalence classes]] of ordinary permutations of these 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. The following four circular permutations on four letters are considered to be the same.

<pre>
     1           4           2           3
   4   3       2   1       3   4       1   2
     2           3           1           4
</pre>

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.
<pre>
     1          1
   4   3      3   4
     2          2</pre>

There are (''n''&thinsp;–&thinsp;1)! circular permutations of a set with ''n'' elements.

==Properties==
The number of permutations of {{math|''n''}} distinct objects is {{math|''n''}}!.

The number of {{math|''n''}}-permutations with {{math|''k''}} disjoint cycles is the signless [[Stirling number of the first kind]], denoted <math>c(n,k)</math> or <math>[\begin{smallmatrix}n \\ k\end{smallmatrix}]</math>.{{sfn|Bona|2012|pp=97–103}}

===Cycle type===
<!-- linked from redirects [[Cycle type]], [[Cycle structure]], and [[Cycle shape]] -->
The cycles (including the fixed points) of a permutation <math>\sigma</math> of a set with {{mvar|n}} elements partition that set; so the lengths of these cycles form an [[integer partition]] of {{mvar|n}}, which is called the '''cycle type''' (or sometimes '''cycle structure''' or '''cycle shape''') of <math>\sigma</math>. There is a "1" in the cycle type for every fixed point of <math>\sigma</math>, a "2" for every transposition, and so on. The cycle type of <math>\beta = (1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)</math> is <math>(3, 2, 2, 1).</math>

This may also be written in a more compact form as {{math|[1<sup>1</sup>2<sup>2</sup>3<sup>1</sup>]}}.
More precisely, the general form is <math>[1^{\alpha_1}2^{\alpha_2}\dotsm n^{\alpha_n}]</math>, where <math>\alpha_1,\ldots,\alpha_n</math> are the numbers of cycles of respective length. The number of permutations of a given cycle type is<ref>{{citation|last = Sagan|first = Bruce|title = The Symmetric Group|publisher = Springer | date = 2001 | edition = 2 | page = 3}}</ref>
: <math>\frac{n!}{1^{\alpha_1}2^{\alpha_2}\dotsm n^{\alpha_n}\alpha_1!\alpha_2!\dotsm \alpha_n!}</math>.

The number of cycle types of a set with {{mvar|n}} elements equals the value of the [[Partition function (number theory)|partition function]] <math>p(n)</math>.

[[Pólya enumeration theorem|Polya]]'s [[cycle index]] polynomial is a [[generating function]] which counts permutations by their cycle type.

===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 [[conjugacy class|conjugating]] a permutation <math>\sigma</math> by another permutation <math>\pi</math>, which means forming the product <math>\pi\sigma\pi^{-1}</math>. Here, <math>\pi\sigma\pi^{-1}</math> is the ''conjugate'' of <math>\sigma</math> by <math>\pi</math> and its cycle notation can be obtained by taking the cycle notation for <math>\sigma</math> and applying <math>\pi</math> to all the entries in it.{{sfn|Humphreys|1996|p=84}} It follows that two permutations are conjugate exactly when they have the same cycle type.

===Order of a permutation===
The order of a permutation <math>\sigma</math> is the smallest positive integer ''m'' so that <math>\sigma^m = \mathrm{id}</math>. It is the [[least common multiple]] of the lengths of its cycles. For example, the order of <math>\sigma=(152)(34) </math> is <math>\text{lcm}(3,2) = 6</math>.

===Parity of a permutation===
{{main|Parity of a permutation}}

Every permutation of a finite set can be expressed as the product of transpositions.<ref>{{harvnb|Hall|1959|p=60}}</ref>
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 and odd permutations|even or odd]] depending on this number.

This result can be extended so as to assign a ''sign'', written <math>\operatorname{sgn}\sigma</math>, to each permutation. <math>\operatorname{sgn}\sigma = +1</math> if <math>\sigma</math> is even and <math>\operatorname{sgn}\sigma = -1</math> if <math>\sigma</math> is odd. Then for two permutations <math>\sigma</math> and <math>\pi</math>

: <math>\operatorname{sgn}(\sigma\pi) = \operatorname{sgn}\sigma\cdot\operatorname{sgn}\pi.</math>

It follows that <math>\operatorname{sgn}\left(\sigma\sigma^{-1}\right) = +1.</math>

The sign of a permutation is equal to the determinant of its permutation matrix (below).

===Matrix representation===
{{main|Permutation matrix}}

A ''permutation matrix'' is an [[Square matrix|''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 ways to assign a permutation matrix to a permutation of {1, 2, ..., ''n''}. One natural approach is to define <math>L_{\sigma}</math> to be the [[Linear map|linear transformation]] of <math>\mathbb{R}^n</math> which permutes the [[standard basis]] <math>\{\mathbf{e}_1,\ldots,\mathbf{e}_n\}</math> by <math>L_\sigma(\mathbf{e}_j)=\mathbf{e}_{\sigma(j)}</math>, and define <math>M_{\sigma}</math> to be its matrix. That is, <math>M_{\sigma}</math> has its ''j''<sup>th</sup> column equal to the n × 1 column vector <math>\mathbf{e}_{\sigma(j)}</math>: its (''i'', ''j'') entry is to 1 if ''i'' = ''σ''(''j''), and 0 otherwise. Since composition of linear mappings is described by matrix multiplication, it follows that this construction is compatible with composition of permutations:<blockquote><math>M_\sigma M_\tau = M_{\sigma\tau}</math>.  </blockquote>For example, the one-line permutations <math>\sigma=213,\ \tau=231</math> have product <math>\sigma\tau = 132</math>, and the corresponding matrices are:<math display="block">
M_{\sigma} M_{\tau} 
= \begin{pmatrix} 0&1&0\\1&0&0\\0&0&1\end{pmatrix}
\begin{pmatrix} 0&0&1\\1&0&0\\0&1&0\end{pmatrix} 
= \begin{pmatrix} 1&0&0\\0&0&1\\0&1&0\end{pmatrix} 
= M_{\sigma\tau}.</math>

[[File:Symmetric group 3; Cayley table; matrices.svg|thumb|Composition of permutations corresponding to a multiplication of permutation matrices.]]
It is also common in the literature to find the inverse convention, where a permutation ''σ'' is associated to the matrix <math>P_{\sigma} = (M_{\sigma})^{-1} = (M_{\sigma})^{T}</math> 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, <math>P_\sigma P_{\tau} = P_{\tau\sigma}</math>.  In this correspondence, permutation matrices act on the right side of the standard <math>1 \times n</math> row vectors <math>({\bf e}_i)^T</math>: <math>({\bf e}_i)^T P_{\sigma} = ({\bf e}_{\sigma(i)})^T</math>.

The [[Cayley table]] 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]] so that any two elements can be compared. The set {1, 2, ..., ''n''} with the usual ≤ relation is the most frequently used set in these applications.

A number of properties of a permutation are directly related to the total ordering of ''S,'' considering the permutation written in one-line notation as a sequence <math>\sigma = \sigma(1)\sigma(2)\cdots\sigma(n)</math>.

===Ascents, descents, runs, exceedances, records===
{{anchor|Descents}}
An ''ascent'' of a permutation&nbsp;''σ'' of ''n'' is any position ''i''&nbsp;&lt;&nbsp;''n'' where the following value is bigger than the current one. That is, ''i'' is an ascent if <math>\sigma(i)<\sigma(i{+}1)</math>. For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.

Similarly, a ''descent'' is a position ''i''&nbsp;&lt;&nbsp;''n'' with <math>\sigma(i)>\sigma(i{+}1)</math>, so every ''i'' with <math>1 \leq i<n</math> is either an ascent or a descent.

An ''ascending run'' of a permutation is a nonempty increasing contiguous subsequence 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&nbsp;1). By contrast an ''increasing subsequence'' of a permutation is not necessarily contiguous: it is an increasing sequence obtained by omitting some of the values of the one-line notation.
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''&nbsp;−&nbsp;1 descents, then it must be the union of ''k'' ascending runs.{{sfn|Bóna|2004|p=4f}}

The number of permutations of ''n'' with ''k'' ascents is (by definition) the [[Eulerian number]] <math>\textstyle\left\langle{n\atop k}\right\rangle</math>; this is also the number of permutations of ''n'' with ''k'' descents. Some authors however define the Eulerian number <math>\textstyle\left\langle{n\atop k}\right\rangle</math> as the number of permutations with ''k'' ascending runs, which corresponds to {{math|''k'' − 1}} descents.{{sfn|Bona|2012|pages=4–5}}

An exceedance of a permutation ''σ''<sub>1</sub>''σ''<sub>2</sub>...''σ''<sub>''n''</sub> is an index ''j'' such that {{math|''σ''<sub>''j''</sub> > ''j''}}. If the inequality is not strict (that is, {{math|''σ''<sub>''j''</sub> ≥ ''j''}}), then ''j'' is called a ''weak exceedance''. The number of ''n''-permutations with ''k'' exceedances coincides with the number of ''n''-permutations with ''k'' descents.{{sfn|Bona|2012|page=25}}

A ''record'' or ''left-to-right maximum'' of a permutation ''σ'' is an element ''i'' such that ''σ''(''j'') < ''σ''(''i'') for all ''j < i''.

=== Foata's transition lemma ===
[[Dominique Foata|Foata]]'s ''fundamental bijection'' transforms a permutation <math>\sigma  </math> with a given canonical cycle form into the permutation <math>f(\sigma) = \hat\sigma   </math> whose one-line notation has the same sequence of elements with parentheses removed.<ref name="Stanley2012" />{{sfn|Bona|2012|pp=109–110}} For example:<blockquote><math>\sigma = (513)(6)(827)(94)
= \begin{pmatrix}
1&2&3&4&5&6&7&8&9\\
3&7&5&9&1&6&8&2&4
\end{pmatrix},

  </math>

<math>\hat\sigma = 513682794
= \begin{pmatrix}
1&2&3&4&5&6&7&8&9\\
5&1&3&6&8&2&7&9&4
\end{pmatrix}.

  </math></blockquote>Here the first element in each canonical cycle of <math>\sigma  </math> becomes a record (left-to-right maximum) of <math>\hat\sigma

  </math>. Given <math>\hat\sigma

  </math>, one may find its records and insert parentheses to construct the inverse transformation <math>\sigma=f^{-1}(\hat\sigma)

  </math>. Underlining the records in the above example: <math>\hat\sigma = \underline{5}\, 1\, 3\, \underline{6}\, \underline{8}\,2\,7\,\underline{9}\,4

  </math>, which allows the reconstruction of the cycles of <math>\sigma  </math>.

The following table shows <math>\hat\sigma  </math> and <math>\sigma  </math> for the six permutations of ''S'' = {1, 2, 3}, with the bold text on each side showing the notation used in the bijection: one-line notation for <math>\hat\sigma  </math> and canonical cycle notation for <math>\sigma  </math>.

{| class="wikitable"
|-
! <math>\hat\sigma = f(\sigma)</math>             !! <math>\sigma=f^{-1}(\hat\sigma)</math> 
|-
| <math>\mathbf{123}=(\,1\,)(\,2\,)(\,3\,)</math> || <math>123=\mathbf{(\,1\,)(\,2\,)(\,3\,)}</math> 
|-
| <math>\mathbf{132}=(\,1\,)(\,3\,2\,)</math>   || <math>132=\mathbf{(\,1\,)(\,3\,2\,)}</math> 
|-
| <math>\mathbf{213}=(\,2\,1\,)(\,3\,)</math>   || <math>213=\mathbf{(\,2\,1\,)(\,3\,)}</math> 
|-
| <math>\mathbf{231}=(\,3\,1\,2\,)</math>     || <math>321=\mathbf{(\,2\,)(\,3\,1\,)}</math> 
|-
| <math>\mathbf{312}=(\,3\,2\,1\,)</math>     || <math>231=\mathbf{(\,3\,1\,2\,)}</math> 
|-
| <math>\mathbf{321}=(\,2\,)(\,3\,1\,)</math>   || <math>312=\mathbf{(\,3\,2\,1\,)}</math> 
|}

As a first corollary, the number of ''n''-permutations with exactly ''k'' records is equal to the number of ''n''-permutations with exactly ''k'' cycles: this last number is the signless [[Stirling number of the first kind]], <math>c(n, k)</math>. Furthermore, Foata's mapping takes an ''n''-permutation with ''k'' weak exceedances to an ''n''-permutation with {{math|''k'' − 1}} ascents.{{sfn|Bona|2012|pp=109–110}}  For example, (2)(31) = 321 has ''k ='' 2 weak exceedances (at index 1 and 2), whereas {{math|''f''(321) {{=}} 231}} has {{math|1=''k'' − 1 = 1}} ascent (at index 1; that is, from 2 to 3).

===Inversions===
{{main|Inversion (discrete mathematics)}}
[[Image:15-Puzzle.jpg|thumb|In the [[15 puzzle]] the goal is to get the squares in ascending order.  Initial positions which have an odd number of inversions are impossible to solve.<ref name="Slocum">{{cite web
  | last1     = Slocum
  | first1    = Jerry
  | last2     = Weisstein
  | first2    = Eric W.
  | title = 15 – puzzle
  | work = MathWorld
  | publisher = Wolfram Research, Inc.
  | date = 1999
  | url = http://mathworld.wolfram.com/15Puzzle.html
  | access-date = October 4, 2014
}}</ref>]]

An ''[[inversion (discrete mathematics)|inversion]]'' of a permutation&nbsp;''σ'' is a pair {{math|(''i'', ''j'')}} of positions where the entries of a permutation are in the opposite order: <math>i < j</math> and <math>\sigma(i)> \sigma(j)</math>.{{sfn|Bóna|2004|p=43}}  Thus a descent is an inversion at two adjacent positions. For example, {{math|''σ'' {{=}} 23154}} has (''i'', ''j'') = (1, 3), (2, 3), and (4, 5), where (''σ''(''i''), ''σ''(''j'')) = (2, 1), (3, 1), and (5, 4).

Sometimes an inversion is defined as the pair of values (''σ''(''i''), ''σ''(''j'')); this makes no difference for the ''number'' of inversions, and the reverse pair (''σ''(''j''), ''σ''(''i'')) is an inversion in the above sense for the inverse permutation ''σ''<sup>−1</sup>.

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 ''σ''<sup>−1</sup>. 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]]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 {{math|''i'' + 1}} 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&nbsp;1; as long as this number is not zero, the permutation is not the identity, so it has at least one descent. [[Bubble sort]] and [[insertion sort]] 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]].{{sfn|Bóna|2004|pp=43ff}} This is the coefficient of <math>q^k</math> in the expansion of the product

<math display="block">[n]_q! = \prod_{m=1}^n\sum_{i=0}^{m-1}q^i = 
1 \left(1 + q\right)\left(1 + q + q^2\right) \cdots \left(1 + q + q^2 + \cdots + q^{n-1}\right),</math>

The notation <math>[n]_q!</math> denotes the [[q-factorial]]. This expansion commonly appears in the study of [[Necklace (combinatorics)|necklaces]].

Let <math>\sigma \in S_n, i, j\in \{1, 2, \dots, n\} </math> such that <math>i<j</math> and <math>\sigma(i)>\sigma(j)</math>.
In this case, say the weight of the inversion <math>(i, j)</math> is <math>\sigma(i)-\sigma(j)</math>.
Kobayashi (2011) proved the enumeration formula 
<math display="block">\sum_{i<j, \sigma(i)>\sigma(j)}(\sigma(i)-\sigma(j)) = |\{\tau \in S_n \mid \tau\le \sigma, \tau \text{ is bigrassmannian}\}</math>

where <math>\le</math> denotes [[Bruhat order]] in the [[symmetric group]]s. This graded partial order often appears in the context of [[Coxeter group]]s.

==Permutations in computing==
===Numbering permutations===
<!-- linked from redirect [[Rothe diagram]] -->
One way to represent permutations of ''n'' things is by an integer ''N'' with 0&nbsp;≤&nbsp;''N''&nbsp;&lt;&nbsp;''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''&nbsp;≤&nbsp;12, and for 64-bit words this means ''n''&nbsp;≤&nbsp;20. The conversion can be done via the intermediate form of a sequence of numbers ''d''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub>, where ''d''<sub>''i''</sub> is a non-negative integer less than ''i'' (one may omit ''d''<sub>1</sub>, 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]]'', which is just a particular [[mixed radix]] representation, where, for numbers less than ''n''!, the bases (place values or multiplication factors) for successive digits are {{math|(''n'' − 1)!}}, {{math|(''n'' − 2)!}}, ..., 2!, 1!. The second step interprets this sequence as a [[Lehmer code]] or (almost equivalently) as an inversion table.

{| class="wikitable" style="float:right; text-align:center; margin: 1em"
|+ Rothe diagram for <math>\sigma = (6, 3, 8, 1, 4, 9, 7, 2, 5)</math>
|-
! {{diagonal split header|<sub>''i''</sub>| <sup>''σ''<sub>''i''</sub></sup>}}
! style="width:20pt;"| 1
! style="width:20pt;"| 2
! style="width:20pt;"| 3
! style="width:20pt;"| 4
! style="width:20pt;"| 5
! style="width:20pt;"| 6
! style="width:20pt;"| 7
! style="width:20pt;"| 8
! style="width:20pt;"| 9
! Lehmer code
|-
! 1
| × || × || × || × || × || • ||   ||   ||   || ''d''<sub>9</sub> = 5
|-
! 2
| × || × || • ||   ||   ||   ||   ||   ||   || ''d''<sub>8</sub> = 2
|-
! 3
| × || × ||   || × || × ||   || × || • ||   || ''d''<sub>7</sub> = 5
|-
! 4
| • ||   ||   ||   ||   ||   ||   ||   ||   || ''d''<sub>6</sub> = 0
|-
! 5
|   || × ||   || • ||   ||   ||   ||   ||   || ''d''<sub>5</sub> = 1
|-
! 6
|   || × ||   ||   || × ||   || × ||   || • || ''d''<sub>4</sub> = 3
|-
! 7
|   || × ||   ||   || × ||   || • ||   ||   || ''d''<sub>3</sub> = 2
|-
! 8
|   || • ||   ||   ||   ||   ||   ||   ||   || ''d''<sub>2</sub> = 0
|-
! 9
|   ||   ||   ||   || • ||   ||   ||   ||   || ''d''<sub>1</sub> = 0
|-
! Inversion table
| 3 || 6 || 1 || 2 || 4 || 0 || 2 || 0 || 0 ||
|}
In the '''Lehmer code''' for a permutation&nbsp;''σ'', the number ''d''<sub>''n''</sub> represents the choice made for the first term&nbsp;''σ''<sub>1</sub>, the number ''d''<sub>''n''−1</sub> represents the choice made for the second term
''σ''<sub>2</sub> among the remaining {{math|''n'' − 1}} elements of the set, and so forth. More precisely, each ''d''<sub>''n''+1−''i''</sub> gives the number of ''remaining'' elements strictly less than the term ''σ''<sub>''i''</sub>. Since those remaining elements are bound to turn up as some later term ''σ''<sub>''j''</sub>, the digit ''d''<sub>''n''+1−''i''</sub> counts the ''inversions'' (''i'',''j'') involving ''i'' as smaller index (the number of values ''j'' for which ''i''&nbsp;&lt;&nbsp;''j'' and ''σ''<sub>''i''</sub>&nbsp;&gt;&nbsp;''σ''<sub>''j''</sub>). The '''inversion table''' for&nbsp;''σ'' is quite similar, but here ''d''<sub>''n''+1−''k''</sub> counts the number of inversions (''i'',''j'') where ''k''&nbsp;=&nbsp;''σ''<sub>''j''</sub> occurs as the smaller of the two values appearing in inverted order.{{sfn|Knuth|1973|p=12}}

Both encodings can be visualized by an ''n''&nbsp;by&nbsp;''n'' '''Rothe diagram'''{{#tag:ref|[[Heinrich August Rothe|H. A. Rothe]], ''Sammlung combinatorisch-analytischer Abhandlungen'' '''2''' (Leipzig, 1800), 263–305. Cited in {{harvnb|Knuth|1973|p=14}}}} (named after [[Heinrich August Rothe]]) in which dots at (''i'',''σ''<sub>''i''</sub>) mark the entries of the permutation, and a cross at (''i'',''σ''<sub>''j''</sub>) marks the inversion (''i'',''j''); by the definition of inversions a cross appears in any square that comes both before the dot (''j'',''σ''<sub>''j''</sub>) in its column, and before the dot (''i'',''σ''<sub>''i''</sub>) 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''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub> 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 ''σ''<sub>''i''</sub> to the element in the list that is preceded by ''d''<sub>''n''+1−''i''</sub> other ones, and remove that element from the list. To convert an inversion table ''d''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub> into the corresponding permutation, one can traverse the numbers from ''d''<sub>1</sub> to ''d''<sub>''n''</sub> 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]] (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 (permutation)|signature]] 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''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub> has an ascent {{math|''n'' − ''i''}} if and only if {{math|''d''<sub>''i''</sub> ≥ ''d''<sub>''i''+1</sub>}}.

===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]] (possibly using the [[factorial number system]] 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 data structure|array]] or a [[linked list]], both require (for different reasons) about ''n''<sup>2</sup>/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 [[big O notation|''O''(''n'' log ''n'')]] time.

====Random generation of permutations====
{{Main|Fisher–Yates shuffle}}
For generating [[random permutation]]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''<sub>1</sub>,''d''<sub>2</sub>,...,''d''<sub>''n''</sub> satisfying {{math|0 ≤ ''d''<sub>''i''</sub> &lt; ''i''}} (since ''d''<sub>1</sub> is always zero it may be omitted) and to convert it to a permutation through a [[bijective]] 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]] and [[Frank Yates]].<ref>{{cite book
|author1=Fisher, R.A. |author2=Yates, F. | title = Statistical tables for biological, agricultural and medical research
| orig-year = 1938
| edition = 3rd
| year = 1948
| pages = 26–27
| publisher = Oliver & Boyd
| location = London
| oclc = 14222135
}}</ref>
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''<sub>''i''</sub> 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 [[swap (computer science)|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 (mathematics)|induction]]. 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 <code>''a''[0], ''a''[1], ..., ''a''[''n'' − 1]</code> can be described as follows in [[pseudocode]]:

 '''for''' ''i'' '''from''' ''n'' '''downto''' 2 '''do'''
     ''d<sub>i</sub>'' ← random element of { 0, ..., ''i'' − 1 }
     '''swap''' ''a''[''d<sub>i</sub>''] and ''a''[''i'' − 1]

This can be combined with the initialization of the array <code>''a''[''i''] = ''i''</code> as follows

 '''for''' ''i'' '''from''' 0 '''to''' ''n''−1 '''do'''
     ''d''<sub>''i''+1</sub> ← random element of { 0, ..., ''i'' }
     ''a''[''i''] ← ''a''[''d''<sub>''i''+1</sub>]
     ''a''[''d''<sub>''i''+1</sub>] ← ''i''

If ''d''<sub>''i''+1</sub> = ''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.<ref>{{cite news|author1=Bacher, A. |author2=Bodini, O.|author3=Hwang, H.K.|author4=Tsai, T.H. | title = Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation.
| edition = ACM Trans. Algorithms 13(2): 24:1–24:43
| year = 2017
| pages = 24–43
}}</ref>

====Generation in lexicographic order====
There are many ways to systematically generate all permutations of a given sequence.<ref name=sedegewick1977>{{cite journal
|last=Sedgewick|first=R
|title=Permutation generation methods
|journal=Computing Surveys|year=1977|volume=9
|issue=2
|pages=137–164
|url=http://www.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf |archive-url=https://web.archive.org/web/20080221185652/http://www.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf |archive-date=2008-02-21 |url-status=live
|doi=10.1145/356689.356692
|s2cid=12139332
}}</ref>
One classic, simple, and flexible algorithm is based upon finding the next permutation in [[lexicographic ordering]], 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]]) and converting those to permutations. It begins by sorting the sequence in (weakly) [[increasing]] 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]]a in 14th century India, and has been rediscovered frequently.{{sfn|Knuth|2005|pp=1–26}}

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 {{math|''a''[''k''] < ''a''[''k'' + 1]}}.  If no such index exists, the permutation is the last permutation.
# Find the largest index ''l'' greater than ''k'' such that {{math|''a''[''k''] < ''a''[''l'']}}.
# Swap the value of ''a''[''k''] with that of ''a''[''l''].
# Reverse the sequence from ''a''[''k'' + 1] up to and including the final element ''a''[''n''].
For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is [[Zero-based numbering|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'' + 1] which 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''[2] and ''a''[3] are swapped to form the new sequence [1, 2, 4, 3].
# The sequence after ''k''-index ''a''[2] 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: [1, 2, 4, 3].
Following this algorithm, the next lexicographic permutation will be [1, 3, 2, 4], and the 24th permutation will be [4, 3, 2, 1] at which point ''a''[''k''] < ''a''[''k'' + 1] does 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.<ref>{{cite web|title=std::next_permutation|url=http://en.cppreference.com/w/cpp/algorithm/next_permutation|access-date=31 March 2018|work=cppreference.com|date=4 December 2017}}</ref>

====Generation with minimal changes====
{{main|Steinhaus–Johnson–Trotter algorithm|Heap's algorithm}}
An alternative to the above algorithm, the [[Steinhaus–Johnson–Trotter algorithm]], 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.{{sfn|Knuth|2005|pp=1–26}}

An alternative to Steinhaus–Johnson–Trotter is [[Heap's algorithm]],<ref>{{cite journal|last=Heap|first=B. R.|title=Permutations by Interchanges|journal=The Computer Journal|year=1963|volume=6|issue=3|pages=293–298|doi=10.1093/comjnl/6.3.293|doi-access=free}}</ref> said by [[Robert Sedgewick (computer scientist)|Robert Sedgewick]] in 1977 to be the fastest algorithm of generating permutations in applications.<ref name=sedegewick1977/>

The following figure shows the output of all three aforementioned algorithms for generating all permutations of length <math>n=4</math>, and of six additional algorithms described in the literature.
[[File:Permutation generation algorithms10.svg|thumb|center|upright=2.2|Ordering of all permutations of length <math>n=4</math> generated by different algorithms. The permutations are color-coded, where {{legend-inline|red|1}}, {{legend-inline|yellow|2}}, {{legend-inline|green|3}}, {{legend-inline|blue|4}}.<ref>{{cite web|url=http://combos.org/perm|title=Generate permutations|last1=Mütze|first1=Torsten|last2=Sawada|first2=Joe|last3=Williams|first3=Aaron|website=Combinatorial Object Server|access-date=May 29, 2019}}</ref>]]

# Lexicographic ordering;
# [[Steinhaus–Johnson–Trotter algorithm]];
# [[Heap's algorithm]];
# Ehrlich's star-transposition algorithm:{{sfn|Knuth|2005|pp=1–26}} in each step, the first entry of the permutation is exchanged with a later entry;
# Zaks' prefix reversal algorithm:<ref name="Zaks_1984">{{cite journal|last=Zaks|first=S.|title=A new algorithm for generation of permutations|journal=[[BIT Numerical Mathematics]]|year=1984|volume=24|issue=2|pages=196–204|doi=10.1007/BF01937486|s2cid=30234652}}</ref> in each step, a prefix of the current permutation is reversed to obtain the next permutation;
# Sawada-Williams' algorithm:<ref>{{cite conference |title=A Hamilton path for the sigma-tau problem |last1=Sawada |first1=Joe |last2=Williams |first2=Aaron |date=2018 |publisher=[[Society for Industrial and Applied Mathematics]] (SIAM) | book-title=Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |pages=568–575 |location=New Orleans, Louisiana |doi=10.1137/1.9781611975031.37|doi-access=free }}</ref> 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:<ref name="Corbett_1992">{{cite journal|last=Corbett|first=P. F.|title=Rotator graphs: An efficient topology for point-to-point multiprocessor networks|journal=IEEE Transactions on Parallel and Distributed Systems|year=1992|volume=3|issue=5|pages=622–626|doi=10.1109/71.159045}}</ref> each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;
# Single-track ordering:<ref name="Arndt_2011">{{cite book |author-last=Arndt |author-first=Jörg|title=Matters Computational. Ideas, Algorithms, Source Code| date=2011| publisher=[[Springer Science+Business Media|Springer]]| doi=10.1007/978-3-642-14764-7|isbn=978-3-642-14763-0}}</ref> each column is a cyclic shift of the other columns;
# Single-track Gray code:<ref name="Arndt_2011"/> each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions.
# Nested swaps generating algorithm in steps connected to the nested subgroups <math>S_k\subset S_{k+1}</math>. Each permutation is obtained from the previous by a transposition multiplication to the left. Algorithm is connected to the [[Factorial_number_system]] of the index.

====Generation of permutations in nested swap steps====
Explicit sequence of swaps (transpositions, 2-cycles <math>(pq)</math>), is described here, each swap applied (on the left) to the previous chain providing a new permutation, such that all the permutations can be retrieved, each only once.<ref>{{cite book
|author1=Popp, O.T. | title = Quickly Handling Big Permutations
| orig-year = 
| edition = 
| year = 2002
| pages = 
| publisher = priv. comm.
| location = 
| oclc = 
}}</ref> This counting/generating procedure has an additional structure (call it nested), as it is given in steps: after completely retrieving <math>S_{k-1}</math>, continue retrieving <math>S_{k}\backslash S_{k-1}</math> by cosets <math>S_{k-1}\tau_i</math> of <math>S_{k-1}</math> in <math>S_k</math>,  by appropriately choosing the coset representatives <math>\tau_i</math> to be described below. Note that, since each <math>S_m</math> is sequentially generated, there is a ''last element'' <math>\lambda_m\in S_m</math>. So, after generating <math>S_{k-1}</math> by swaps, the next permutation in <math>S_{k}\backslash S_{k-1}</math>  has to be <math>\tau_1=(p_1k)\lambda_{k-1}</math> for some <math>1\leq p_1<k</math>. Then all swaps that generated  <math>S_{k-1}</math> are repeated, generating the whole coset <math>S_{k-1}\tau_1</math>, reaching the last permutation in that coset <math>\lambda_{k-1}\tau_1</math>; the next swap has to move the permutation to representative of another coset <math>\tau_2=(p_2k)\lambda_{k-1}\tau_1</math>. 

Continuing the same way, one gets coset representatives <math>\tau_j=(p_{j}k)\lambda_{k-1}\cdots \lambda_{k-1}(p_{i}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{1}k)\lambda_{k-1}</math> for the cosets of  <math>S_{k-1}</math> in <math>S_k</math>; the ordered set <math>(p_1,\ldots , p_{k-1})</math> (<math>0\leq p_i<k</math>) is called the set of coset beginnings. Two of these representatives are in the same coset if and only if  <math>\tau_j(\tau_i)^{-1}=(p_{j}k)\lambda_{k-1}(p_{j-1}k)\lambda_{k-1}\cdots \lambda_{k-1}(p_{i+1}k)=\varkappa_{ij}\in S_{k-1}</math>, that is,  <math>\varkappa_{ij} (k)=k</math>. Concluding, permutations <math>\tau_i\in S_k-S_{k-1}</math> are all representatives of distinct cosets if and only if for any <math>k>j>i\geq 1</math>, <math>(\lambda_{k-1})^{j-i}p_{i}\neq p_j</math> (no repeat condition).  In particular, for all generated permutations to be distinct it is not necessary for the <math>p_i</math> values to be distinct. In the process, one gets that <math>\lambda_k=\lambda_{k-1}(p_{k-1}k)\lambda_{k-1}(p_{k-2}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{1}k)\lambda_{k-1}</math> and this provides the recursion procedure. 

EXAMPLES: obviously, for <math>\lambda_2</math> one has <math>\lambda_2=(12)</math>; to build <math>\lambda_3</math> there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice <math> p_1=p_2=1</math> leads to <math>\lambda_3=\lambda_2(13)\lambda_2(13)\lambda_2=(13)</math>. To continue generating <math>S_4</math> one needs appropriate  coset beginnings (satisfying the no repeat condition): there is a convenient choice: <math>p_1=1, p_2=2, p_3=3</math>, leading to  <math>\lambda_4=(13)(1234)(13)=(1432)</math>. Then, to build <math>\lambda_5</math> a convenient choice for the coset beginnings (satisfying the no repeat condition) is <math> p_1=p_2=p_3=p_4=1</math>, leading to <math>\lambda_5=(15)</math>. 

From examples above one can inductively go to higher <math>k</math> in a similar way, choosing coset beginnings of <math>S_{k}</math> in  <math>S_{k+1}</math>, as follows: for <math>k</math> even choosing all coset beginnings equal to 1 and for <math>k</math> odd choosing coset beginnings equal to <math>(1, 2,\dots , k)</math>. With such choices the "last" permutation is <math>\lambda_k=(1k)</math> for <math>k</math> odd and  <math>\lambda_k=(1k_-)(12\cdots k)(1k_-)</math> for <math>k</math> even (<math>k_-=k-1</math>). Using these explicit formulae one can easily compute the permutation of certain index in the counting/generation steps with minimum computation. For this, writing the index in factorial base is useful. For example, the permutation for index <math>699=5(5!)+4(4!)+1(2!)+1(1!)</math> is: <math>\sigma=\lambda_2(13)\lambda_2(15)\lambda_4(15)\lambda_4(15)\lambda_4(15)\lambda_4(56)\lambda_5(46)\lambda_5(36)\lambda_5(26)\lambda_5(16)\lambda_5=</math> <math>\lambda_2(13)\lambda_2((15)\lambda_4)^4(\lambda_5)^{-1}\lambda_6=(23)(14325)^{-1}(15)(15)(123456)(15)=</math><math>(23)(15234)(123456)(15)</math>, yelding finally, <math>\sigma=(1653)(24)</math>.

Because multiplying by swap permutation  takes  short computing time and every new generated permutation requires only one such swap multiplication, this generation procedure is quite efficient. Moreover as there is a simple formula, having the last permutation in each <math>S_k</math>  can save even more time to go directly to a permutation with certain index in fewer steps than expected as it can be done in blocks of subgroups rather than swap by swap.

===Applications===
Permutations are used in the [[interleaver]] component of the  [[error detection and correction]] algorithms, such as [[turbo codes]], for example [[3GPP Long Term Evolution]]  mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212<ref>{{cite web| url = http://www.3gpp.org/ftp/Specs/html-info/36212.htm| title = 3GPP TS 36.212}}</ref>).
Such applications raise the question of fast generation of permutations satisfying certain desirable properties. One of the methods is based on the [[permutation polynomials]]. Also as a base for optimal hashing in Unique Permutation Hashing.<ref>{{cite journal |first1=Shlomi |last1=Dolev |first2=Limor |last2=Lahiani |first3=Yinnon |last3=Haviv |title=Unique permutation hashing |journal=Theoretical Computer Science |volume=475 |year=2013 |pages=59–65 |doi=10.1016/j.tcs.2012.12.047 |doi-access=free }}</ref>

==See also==
{{Portal|Mathematics}}
{{Div col|colwidth=15em}}
* [[Alternating permutation]]
* [[Convolution]]
* [[Cyclic order]]
* [[Even and odd permutations]]
* [[Josephus permutation]]
* [[Levi-Civita symbol]]
* [[List of permutation topics]]
* [[Major index]]
* [[Permutation category]]
* [[Permutation group]]
* [[Permutation pattern]]
* [[Permutation representation (symmetric group)]]
* [[Probability]]
* [[Rencontres numbers]]
* [[Sorting network]]
* [[Substitution cipher]]
* [[Superpattern]]
* [[Superpermutation]]
* [[Twelvefold way]]
* [[Weak order of permutations]]
{{div col end}}

==Notes==
<!-- {{notelist|30em}} -->
{{notelist}}

==References==
{{Reflist|30em}}

==Bibliography==
* {{citation|first=Kenneth P.|last=Bogart|title=Introductory Combinatorics|edition=2nd|year=1990|publisher=Harcourt Brace Jovanovich|isbn=978-0-15-541576-8}}
* {{citation|first=Miklós|last=Bóna|author-link=Miklós Bóna|title=Combinatorics of Permutations|publisher= Chapman Hall-CRC|year=2004|isbn=978-1-58488-434-7}}
* {{citation|first=Miklos|last=Bona|title=Combinatorics of Permutations|edition=2nd|year=2012|publisher=CRC Press|isbn=978-1-4398-5051-0}}
* {{citation|first=Richard A.|last=Brualdi|title=Introductory Combinatorics|edition=5th|publisher=Prentice-Hall|year=2010|isbn=978-0-13-602040-0}}
* {{citation|first=Peter J.|last=Cameron|title=Combinatorics: Topics, Techniques, Algorithms|year=1994|publisher=Cambridge University Press|isbn=978-0-521-45761-3}}
* {{citation|first=Robert D.|last=Carmichael|title=Introduction to the theory of Groups of Finite Order|year=1956|orig-year=1937|publisher=Dover|isbn=978-0-486-60300-1}}
* {{ citation | last1 = Fraleigh | first1 = John B. | year = 1976 | isbn = 0-201-01984-1 | title = A First Course In Abstract Algebra | edition = 2nd | publisher = [[Addison-Wesley]] | location = Reading }}
* {{citation|first=Larry J.|last=Gerstein|title=Discrete Mathematics and Algebraic Structures|year=1987|publisher=W.H. Freeman and Co.|isbn=978-0-7167-1804-8|url-access=registration|url=https://archive.org/details/discretemathemat0000gers}}
* {{citation| first=Marshall Jr. |last=Hall|author-link=Marshall Hall (mathematician)|title=The Theory of Groups|year=1959|publisher=MacMillan}}
* {{citation|last=Humphreys|first=J. F.|title=A course in group theory|publisher=Oxford University Press|year=1996|isbn=978-0-19-853459-4|url={{Google books|plainurl=y|id=2p3_ngEACAAJ|page=84|text=conjugate permutations have the same cycle type}}}}
* {{citation|first=Donald|last=Knuth|series=The Art of Computer Programming|volume=3|title=Sorting and Searching|year=1973}}  This book mentions the Lehmer code (without using that name) as a variant ''C''<sub>1</sub>,...,''C''<sub>''n''</sub> of inversion tables in exercise 5.1.1–7 (p.&nbsp;19), together with two other variants.
* {{citation|first=Donald|last=Knuth|author-link=Donald Knuth|series=[[The Art of Computer Programming]]|volume=4|title=Generating All Tuples and Permutations|publisher=Addison–Wesley|year=2005|isbn=978-0-201-85393-3}} Fascicle&nbsp;2, first printing.
* {{ citation | first1 = Neal H. | last1 = McCoy | year = 1968 | title = Introduction To Modern Algebra, Revised Edition | publisher = [[Allyn and Bacon]] | location = Boston | lccn = 68015225 }}
* {{ citation | first1 = Evar D. | last1 = Nering | year = 1970 | title = Linear Algebra and Matrix Theory | edition = 2nd | publisher = [[John Wiley & Sons|Wiley]] | location = New York | lccn = 76091646 }}
* {{citation|first=Joseph J.|last=Rotman|title=Advanced Modern Algebra|year=2002|publisher=Prentice-Hall|isbn=978-0-13-087868-7}}
* {{citation|last=Stedman|first=Fabian|author-link=Fabian Stedman|title=Campanalogia|year=1677|place=London}}  The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the [[Ancient Society of College Youths|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".''
* {{citation| first=James|last=Uspensky|author-link=J. V. Uspensky|title=Introduction to Mathematical Probability|year=1937|publisher=McGraw-Hill|url=https://archive.org/details/in.ernet.dli.2015.263184/page/n25/mode/2up}}
* {{ citation | title = Webster's Seventh New Collegiate Dictionary | location = Springfield | publisher = [[G. & C. Merriam Company]] | date = 1969 | ref = {{harvid|Webster|1969}} }}

==Further reading==
* {{citation|first=Norman L.|last=Biggs|title=Discrete Mathematics|edition=2nd|year=2002|publisher=Oxford University Press|isbn=978-0-19-850717-8}}
* {{citation | last1=Foata | first1=Dominique | last2=Schutzenberger | first2=Marcel-Paul | title=Théorie Géométrique des Polynômes Eulériens | publisher=Springer-Verlag | location=Berlin, Heidelberg | series=Lecture Notes in Mathematics | volume=138 | year=1970 | isbn=978-3-540-04927-2 | url=http://irma.math.unistra.fr/~foata/paper/pub14.html}}. The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag.
* {{citation|first=Donald|last=Knuth|series=The Art of Computer Programming|volume=3|title=Sorting and Searching|edition=Second|publisher=Addison–Wesley|year=1998|isbn=978-0-201-89685-5|ref=none}}. Section 5.1: Combinatorial Properties of Permutations, pp.&nbsp;11–72.
* {{cite journal|first1=Robert|last1=Sedgewick|doi=10.1145/356689.356692|journal=ACM Computing Surveys|year=1977|volume=9|issue=2|pages=137–164|title=Permutation generation methods|s2cid=12139332|doi-access=free}}
* {{cite journal|first1=Kobayashi|last1=Masato|journal=Order|year=2011|volume=1|pages=131–137|title=Enumeration of bigrassmannian permutations below a permutation in Bruhat order}}

==External links==
{{Commons category|Permutations}}
{{wikiversity|Permutation notation}}
* {{springer|title=Permutation|id=p/p072270}}

{{Authority control}}

[[Category:Factorial and binomial topics| ]]
[[Category:Permutations| ]]
[[Category:Arab inventions]]