Editing Permutation (section)

==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.