Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.13 Permutations: Cycle Notation

Show Annotations
Notes:
See Cameron (1994, pp. 77, 80–84) and Stanley (1997, pp. 20–21, 67).
Defines:
\mathop{\mathfrak{S}_{{n}}\/}\nolimits: set of permutations of \{1,2,\ldots,n\}
Keywords:
Stirling cycle numbers, permutations
Referenced by:
§26.14(i), §26.15
Permalink:
http://dlmf.nist.gov/26.13

\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}.

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}
Show Annotations
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

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:

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

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.

© 2010–2013 NIST / Privacy Policy / Disclaimer / Feedback; Version 1.0.6; Release date 2013-05-06 Math-Image version (See MathML) . A Printed Companionis available.