Cycles and fixed points

In mathematics, the cycles of a permutation pi of a finite set S correspond bijectively to the orbits of the subgroup generated by pi acting on S. These orbits are subsets of S that can be written as , such that pi(ci) = ci + 1 for i = 1, ..., n − 1, and pi(cn) = c1. The corresponding cycle of pi is written as ( c1 c2 ... cn ); this expression is not unique since c1 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 be a permutation that maps 1 to 2, 6 to 8, etc. Then one may write pi = ( 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 pi, since pi(5) = 5 and pi(7)=7. It is typical, but not necessary, to not write the cycles of length one in such an expression. Thus, pi = (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. The unsigned Stirling number of the first kind, s(k, j) counts the number of permutations of k elements with exactly j disjoint cycles. (1) For every k > 0 : s(k, k) = 1. (2) For every k > 0 : s(k, 1) = (k − 1)!. (3) For every k > j > 1, s(k, j) = s(k − 1,j − 1) + s(k − 1, j)·(k − 1) (1) There is only one way to construct a permutation of k elements with k cycles: Every cycle must have length 1 so every element must be a fixed point. (2.a) Every cycle of length k may be written as permutation of the number 1 to k; there are k! of these permutations. (2.b) There are k different ways to write a given cycle of length k, e.g.