# §26.13 Permutations: Cycle Notation

denotes the set of permutations of . is a one-to-one and onto mapping from to itself. An explicit representation of can be given by the matrix:

26.13.1

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

26.13.2

is 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 .

An element of with fixed points, cycles of length cycles of length , where , is said to have cycle type . The number of elements of with cycle type is given by (26.4.7).

The Stirling cycle numbers of the first kind, denoted by , count the number of permutations of with exactly 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, , is the number of elements of 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 can be written as the composition of two-cycles (read from right to left):

Every permutation is a product of transpositions. A permutation with cycle type can be written as a product of transpositions, and no fewer. For the example (26.13.2), this decomposition is given by

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 is a product of adjacent transpositions:

Every permutation is a product of adjacent transpositions. Given a permutation , the inversion number of , denoted , is the least number of adjacent transpositions required to represent . Again, for the example (26.13.2) a minimal decomposition into adjacent transpositions is given by : .