${\U0001d516}_{n}$ denotes the set of permutations of $\{1,2,\mathrm{\dots},n\}$. $\sigma \in {\U0001d516}_{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:

26.13.1 | $$\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 3\hfill & \hfill \mathrm{\cdots}\hfill & \hfill n\hfill \\ \hfill \sigma (1)\hfill & \hfill \sigma (2)\hfill & \hfill \sigma (3)\hfill & \hfill \mathrm{\cdots}\hfill & \hfill \sigma (n)\hfill \end{array}\right].$$ | ||

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 | $$\left[\begin{array}{cccccccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 3\hfill & \hfill 4\hfill & \hfill 5\hfill & \hfill 6\hfill & \hfill 7\hfill & \hfill 8\hfill \\ \hfill 3\hfill & \hfill 5\hfill & \hfill 2\hfill & \hfill 4\hfill & \hfill 7\hfill & \hfill 8\hfill & \hfill 1\hfill & \hfill 6\hfill \end{array}\right]$$ | ||

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 ${\U0001d516}_{n}$ with ${a}_{1}$ fixed points, ${a}_{2}$ cycles of
length $2,\mathrm{\dots},{a}_{n}$ cycles of length $n$, where
$n={a}_{1}+2{a}_{2}+\mathrm{\cdots}+n{a}_{n}$, is said to have *cycle type*
$({a}_{1},{a}_{2},\mathrm{\dots},{a}_{n})$. The number of elements of ${\U0001d516}_{n}$ with cycle type
$({a}_{1},{a}_{2},\mathrm{\dots},{a}_{n})$ is given by (26.4.7).

The *Stirling cycle numbers* of the first kind, denoted by
$\left[\genfrac{}{}{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

26.13.3 | $$\left[\genfrac{}{}{0pt}{}{n}{k}\right]=\left|s(n,k)\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 ${\U0001d516}_{n}$
with no fixed points:

26.13.4 | $$d(n)=n!\sum _{j=0}^{n}{(-1)}^{j}\frac{1}{j!}=\lfloor \frac{n!+\mathrm{e}-2}{\mathrm{e}}\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},\mathrm{\dots},{j}_{k})=({j}_{1},{j}_{2})({j}_{2},{j}_{3})\mathrm{\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},\mathrm{\dots},{a}_{n})$ can be written as a product of ${a}_{2}+2{a}_{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 $(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 $$, then $(j,k)$ is a product of $2k-2j-1$ adjacent transpositions:

26.13.6 | $$(j,k)=(k-1,k)(k-2,k-1)\mathrm{\cdots}(j+1,j+2)(j,j+1)(j+1,j+2)\mathrm{\cdots}(k-1,k).$$ | ||

Every permutation is a product of adjacent transpositions. Given a permutation
$\sigma \in {\U0001d516}_{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
$(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)$:
$inv((1,3,2,5,7)(6,8))=11$.