# §26.13 Permutations: Cycle Notation

$\mathfrak{S}_{n}$ denotes the set of permutations of $\{1,2,\ldots,n\}$. $\sigma\in\mathfrak{S}_{n}$ is a one-to-one and onto mapping from $\{1,2,\ldots,n\}$ to itself. An explicit representation of $\sigma$ can be given by the $2\times n$ matrix:

 26.13.1 $\begin{bmatrix}1&2&3&\cdots&n\\ \sigma(1)&\sigma(2)&\sigma(3)&\cdots&\sigma(n)\end{bmatrix}.$ ⓘ Symbols: $n$: nonnegative integer and $\sigma$: permutation Permalink: http://dlmf.nist.gov/26.13.E1 Encodings: TeX, pMML, png See also: Annotations for §26.13 and Ch.26

In cycle notation, the elements in each cycle are put inside parentheses, ordered so that $\sigma(j)$ immediately follows $j$ or, if $j$ is the last listed element of the cycle, then $\sigma(j)$ is the first element of the cycle. The permutation

 26.13.2 $\begin{bmatrix}1&2&3&4&5&6&7&8\\ 3&5&2&4&7&8&1&6\end{bmatrix}$ ⓘ Referenced by: §26.13, §26.13, §26.13 Permalink: http://dlmf.nist.gov/26.13.E2 Encodings: TeX, pMML, png See also: Annotations for §26.13 and Ch.26

is ${\left(1,3,2,5,7\right)}{\left(4\right)}{\left(6,8\right)}$ in cycle notation. Cycles of length one are fixed points. They are often dropped from the cycle notation. In consequence, (26.13.2) can also be written as ${\left(1,3,2,5,7\right)}{\left(6,8\right)}$.

An element of $\mathfrak{S}_{n}$ with $a_{1}$ fixed points, $a_{2}$ cycles of length $2,\ldots,a_{n}$ cycles of length $n$, where $n=a_{1}+2a_{2}+\cdots+na_{n}$, is said to have cycle type ${\left(a_{1},a_{2},\ldots,a_{n}\right)}$. The number of elements of $\mathfrak{S}_{n}$ with cycle type ${\left(a_{1},a_{2},\ldots,a_{n}\right)}$ is given by (26.4.7).

The Stirling cycle numbers of the first kind, denoted by $\left[n\atop k\right]$, count the number of permutations of $\{1,2,\ldots,n\}$ with exactly $k$ cycles. They are related to Stirling numbers of the first kind by

 26.13.3 $\left[n\atop k\right]=\left|s\left(n,k\right)\right|.$ ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.13.E3 Encodings: TeX, pMML, png See also: Annotations for §26.13 and Ch.26

See §26.8 for generating functions, recurrence relations, identities, and asymptotic approximations.

A derangement is a permutation with no fixed points. The derangement number, $d(n)$, is the number of elements of $\mathfrak{S}_{n}$ with no fixed points:

 26.13.4 $d(n)=n!\sum_{j=0}^{n}(-1)^{j}\frac{1}{j!}=\left\lfloor\frac{n!+\mathrm{e}-2}{% \mathrm{e}}\right\rfloor.$

A transposition is a permutation that consists of a single cycle of length two. An adjacent transposition is a transposition of two consecutive integers. A permutation that consists of a single cycle of length $k$ can be written as the composition of $k-1$ two-cycles (read from right to left):

 26.13.5 ${\left(j_{1},j_{2},\ldots,j_{k}\right)}={\left(j_{1},j_{2}\right)}{\left(j_{2}% ,j_{3}\right)}\cdots{\left(j_{k-2},j_{k-1}\right)}{\left(j_{k-1},j_{k}\right)}.$ ⓘ Symbols: ${\left(\NVar{S}\right)}$: cycle, $j$: nonnegative integer and $k$: nonnegative integer Permalink: http://dlmf.nist.gov/26.13.E5 Encodings: TeX, pMML, png See also: Annotations for §26.13 and Ch.26

Every permutation is a product of transpositions. A permutation with cycle type ${\left(a_{1},a_{2},\ldots,a_{n}\right)}$ can be written as a product of $a_{2}+2a_{3}+\cdots+(n-1)a_{n}=n-(a_{1}+a_{2}+\cdots+a_{n})$ transpositions, and no fewer. For the example (26.13.2), this decomposition is given by ${\left(1,3,2,5,7\right)}{\left(6,8\right)}={\left(1,3\right)}{\left(2,3\right)% }{\left(2,5\right)}{\left(5,7\right)}{\left(6,8\right)}.$

A permutation is even or odd according to the parity of the number of transpositions. The sign of a permutation is $+$ if the permutation is even, $-$ if it is odd.

Every transposition is the product of adjacent transpositions. If $j, then ${\left(j,k\right)}$ is a product of $2k-2j-1$ adjacent transpositions:

 26.13.6 ${\left(j,k\right)}={\left(k-1,k\right)}{\left(k-2,k-1\right)}\cdots{\left(j+1,% j+2\right)}\*{\left(j,j+1\right)}{\left(j+1,j+2\right)}\cdots{\left(k-1,k% \right)}.$ ⓘ Symbols: ${\left(\NVar{S}\right)}$: cycle, $j$: nonnegative integer and $k$: nonnegative integer Permalink: http://dlmf.nist.gov/26.13.E6 Encodings: TeX, pMML, png See also: Annotations for §26.13 and Ch.26

Every permutation is a product of adjacent transpositions. Given a permutation $\sigma\in\mathfrak{S}_{n}$, the inversion number of $\sigma$, denoted $\mathop{\mathrm{inv}}(\sigma)$, is the least number of adjacent transpositions required to represent $\sigma$. Again, for the example (26.13.2) a minimal decomposition into adjacent transpositions is given by ${\left(1,3,2,5,7\right)}{\left(6,8\right)}={\left(2,3\right)}\*{\left(1,2% \right)}\*{\left(4,5\right)}{\left(3,4\right)}{\left(2,3\right)}{\left(3,4% \right)}{\left(4,5\right)}{\left(6,7\right)}{\left(5,6\right)}{\left(7,8\right% )}\*{\left(6,7\right)}$: $\mathop{\mathrm{inv}}({\left(1,3,2,5,7\right)}{\left(6,8\right)})=11$.