§26.13 Permutations: Cycle Notation

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

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

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 ${𝔖}_n$ with $a_1$ fixed points, $a_2$ cycles of length $2,\mathrm{\dots },a_n$ cycles of length $n$, where $n=a_1+2a_2+\mathrm{\cdots }+n{a}_n$, is said to have cycle type $\left(a_1,a_2,\mathrm{\dots },a_n\right)$. The number of elements of ${𝔖}_n$ with cycle type $\left(a_1,a_2,\mathrm{\dots },a_n\right)$ is given by (26.4.7).

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

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 ${𝔖}_n$ with no fixed points:

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):

Every permutation is a product of transpositions. A permutation with cycle type $\left(a_1,a_2,\mathrm{\dots },a_n\right)$ can be written as a product of $a_2+2a_3+\mathrm{\cdots }+(n-1)a_n=n-(a_1+a_2+\mathrm{\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 , then $\left(j,k\right)$ is a product of $2k-2j-1$ adjacent transpositions:

Every permutation is a product of adjacent transpositions. Given a permutation $\sigma \in {𝔖}_n$, the inversion number of $\sigma$, denoted $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)$: $inv(\left(1,3,2,5,7\right)\left(6,8\right))=11$.