§26.13 Permutations: Cycle Notation

$\mathop{\mathfrak{S}_{n}\/}\nolimits$ denotes the set of permutations of $\{1,2,\ldots,n\}$. $\sigma\in\mathop{\mathfrak{S}_{n}\/}\nolimits$ 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

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

is $(1,3,2,5,7)(4)(6,8)$ 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 $(1,3,2,5,7)(6,8)$.

An element of $\mathop{\mathfrak{S}_{n}\/}\nolimits$ 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 $(a_{1},a_{2},\ldots,a_{n})$. The number of elements of $\mathop{\mathfrak{S}_{n}\/}\nolimits$ with cycle type $(a_{1},a_{2},\ldots,a_{n})$ 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|\mathop{s\/}\nolimits\!\left(n,k\right)\right|.$

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 $\mathop{\mathfrak{S}_{n}\/}\nolimits$ with no fixed points:

 26.13.4 $d(n)=n!\sum_{j=0}^{n}(-1)^{j}\frac{1}{j!}=\left\lfloor\frac{n!+e-2}{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 $(j_{1},j_{2},\ldots,j_{k})=(j_{1},j_{2})(j_{2},j_{3})\cdots(j_{k-2},j_{k-1})(j% _{k-1},j_{k}).$

Every permutation is a product of transpositions. A permutation with cycle type $(a_{1},a_{2},\ldots,a_{n})$ 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 $(1,3,2,5,7)(6,8)=(1,3)(2,3)(2,5)(5,7)(6,8).$

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 $(j,k)$ is a product of $2k-2j-1$ adjacent transpositions:

 26.13.6 $(j,k)=(k-1,k)(k-2,k-1)\cdots(j+1,j+2)\*(j,j+1)(j+1,j+2)\cdots(k-1,k).$

Every permutation is a product of adjacent transpositions. Given a permutation $\sigma\in\mathop{\mathfrak{S}_{n}\/}\nolimits$, 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 $(1,3,2,5,7)(6,8)=(2,3)\*(1,2)\*(4,5)(3,4)(2,3)(3,4)(4,5)(6,7)(5,6)(7,8)\*(6,7)$: $\mathop{\mathrm{inv}}((1,3,2,5,7)(6,8))=11$.