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

§26.13 Permutations: Cycle Notation

𝔖n denotes the set of permutations of {1,2,,n}. σ𝔖n is a one-to-one and onto mapping from {1,2,,n} to itself. An explicit representation of σ can be given by the 2×n matrix:

26.13.1 [123nσ(1)σ(2)σ(3)σ(n)].

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

26.13.2 [1234567835247816]

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 𝔖n with a1 fixed points, a2 cycles of length 2,,an cycles of length n, where n=a1+2a2++nan, is said to have cycle type (a1,a2,,an). The number of elements of 𝔖n with cycle type (a1,a2,,an) is given by (26.4.7).

The Stirling cycle numbers of the first kind, denoted by [nk], count the number of permutations of {1,2,,n} with exactly k cycles. They are related to Stirling numbers of the first kind by

26.13.3 [nk]=|s(n,k)|.

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:

26.13.4 d(n)=n!j=0n(-1)j1j!=n!+-2.

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 (j1,j2,,jk)=(j1,j2)(j2,j3)(jk-2,jk-1)(jk-1,jk).

Every permutation is a product of transpositions. A permutation with cycle type (a1,a2,,an) can be written as a product of a2+2a3++(n-1)an=n-(a1+a2++an) 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:

26.13.6 (j,k)=(k-1,k)(k-2,k-1)(j+1,j+2)(j,j+1)(j+1,j+2)(k-1,k).

Every permutation is a product of adjacent transpositions. Given a permutation σ𝔖n, the inversion number of σ, denoted inv(σ), 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 (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.