Editing Permutation (section)

==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, <math display=block>(513)(6)(827)(94)</math> is a permutation of <math>S = \{1, 2, \ldots , 9\}</math> 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>.