16-bit Gray code permutation G
multiplied with the bit-reversal permutation B

G has 2 fixed points, 1 2-cycle and 3 4-cycles
B has 4 fixed points and 6 2-cycles
GB has 2 fixed points and 2 7-cycles

P * (1,2,3,4)^T = (4,1,3,2)^T

Permutation of four elements with 1 fixed point and 1 3-cycle

In mathematics, the cycles of a permutation π of a finite set S correspond bijectively to the orbits of the subgroup generated by π acting on S. These orbits are subsets of S that can be written as { c₁, ..., c_n }, such that

π(c_i) = c_{i + 1} for i = 1, ..., n − 1, and π(c_n) = c₁.

The corresponding cycle of π is written as ( c₁ c₂ ... c_n ); this expression is not unique since c₁ can be chosen to be any element of the orbit.

The size n of the orbit is called the length of the corresponding cycle; when n = 1, the single element in the orbit is called a fixed point of the permutation.

A permutation is determined by giving an expression for each of its cycles, and one notation for permutations consist of writing such expressions one after another in some order. For example, let

${\displaystyle \pi ={\begin{pmatrix}1&6&7&2&5&4&8&3\\2&8&7&4&5&3&6&1\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5&6&7&8\\2&4&1&3&5&8&7&6\end{pmatrix}}}$

be a permutation that maps 1 to 2, 6 to 8, etc. Then one may write

π = ( 1 2 4 3 ) ( 5 ) ( 6 8 ) (7) = (7) ( 1 2 4 3 ) ( 6 8 ) ( 5 ) = ( 4 3 1 2 ) ( 8 6 ) ( 5 ) (7) = ...

Here 5 and 7 are fixed points of π, since π(5) = 5 and π(7)=7. It is typical, but not necessary, to not write the cycles of length one in such an expression.^[1] Thus, π = (1 2 4 3)(6 8), would be an appropriate way to express this permutation.

There are different ways to write a permutation as a list of its cycles, but the number of cycles and their contents are given by the partition of S into orbits, and these are therefore the same for all such expressions.

Counting permutations by number of cycles

The unsigned Stirling number of the first kind, s(k, j) counts the number of permutations of k elements with exactly j disjoint cycles.^[2][3]

Counting permutations by number of fixed points

The value f(k, j) counts the number of permutations of k elements with exactly j fixed points. For the main article on this topic, see rencontres numbers.

Alternate calculations

Equations	Examples
${\displaystyle f(k,1)=\sum _{i=1}^{k}(-1)^{i+1}{k \choose i}i(k-i)!}$	${\displaystyle {\begin{aligned}f(5,1)&=5\times 1\times 4!-10\times 2\times 3!+10\times 3\times 2!-5\times 4\times 1!+1\times 5\times 0!\\&=120-120+60-20+5=45.\end{aligned}}}$
${\displaystyle f(k,0)=k!-\sum _{i=1}^{k}(-1)^{i+1}{k \choose i}(k-i)!}$	${\displaystyle {\begin{aligned}f(5,0)&=120-(5\times 4!-10\times 3!+10\times 2!-5\times 1!+1\times 0!)\\&=120-(120-60+20-5+1)=120-76=44.\end{aligned}}}$
For every k > 1: ${\displaystyle f(k,0)=(k-1)(f(k-1,0)+f(k-2,0))}$	${\displaystyle f(5,0)=4\times (9+2)=4\times 11=44}$
For every k > 1: ${\displaystyle f(k,0)=k!\sum _{i=2}^{k}{\frac {(-1)^{i}}{i!}}}$	${\displaystyle {\begin{aligned}f(5,0)&=120\times (1/2-1/6+1/24-1/120)\\&=120\times (60/120-20/120+5/120-1/120)=120\times 44/120=44\end{aligned}}}$
${\displaystyle f(k,0)\approx {\frac {k!}{e}}}$ where e is Euler's number ≈ 2.71828

See also

• Cyclic permutation
• Cycle notation

Notes

References

• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 0-521-45761-0
• Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman and Co., ISBN 0-7167-1804-9