Cycles and fixed points

Let P be a permutation over a given set S.
We call a subset { c [1] , c [2] , ... , c [n] } of S a cycle of P with length n
iff the permutation maps S in the following way:
p ( c [i] ) = c [i+1] for i = 1, 2, ..., n-1
and p ( c [n] ) = c [1]

It's usual to write a cycle by it's mapping:
( c [1] c [2] ... c [n] )

Every permutation may be written as a combination of disjoint cycles.

Example: Let
$P={\begin{pmatrix}1&6&2&5&4&7&3\\2&7&4&5&3&6&1\end{pmatrix}}={\begin{pmatrix}1&2&4&3&5&6&7\\2&4&3&1&5&7&6\end{pmatrix}}$
be a permutation which maps 1 to 2 etc.
P may be written as P =
( 1 2 4 3 ) ( 5 ) ( 6 7 ) =
( 1 2 4 3 ) ( 6 7 ) ( 5 ) =
( 4 3 1 2 ) ( 7 6 ) ( 5 )

Note:

• There are different ways to write a permutation as a combination of disjoint cycles, but the number of cycles and their contens is always unique.
• In this examples 5 is a fixed point of the permutation, i.e. 5 is mapped to itself. Every fixed point performs a cycle with length 1.

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.

Properties

(1) For every k > 0 : s ( k , k ) = 1
.
(2) For every k > 0 : s ( k , 1 ) = ( k-1 ) ! ( where "!" means "Factorial" )
.
(3) For every k > j > 1 :
    s ( k , j ) = s ( k-1 , j-1 )
                + s ( k-1 , j   ) * ( k-1 )

Reason of properties

(1) There is only one possibility 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 this permutations.
(2.b) There are k different ways to write a given cycle of length k, e.g. ( 1 2 4 3 ) = ( 2 4 3 1 ) = ( 4 3 1 2 ) = ( 3 1 2 4 ).
(2.c) Finally: s ( k , 1 ) = k! / k = ( k-1) !

(3) There are 2 different methods to construct a permutation of k elements with j cycles:
(3.a) If we want element k to be a fixed point we may choose one of the s ( k-1 , j-1 ) permutations with k-1 elements and j-1 circles and add element k as a new circle of length 1.
(3.a) If we want element k to be not a fixed point we may choose one of the s ( k-1 , j ) permutations with k-1 elements and j circles and insert element k in an existing circle in front of one of the k-1 elements.

Some values

k	j
	1	2	3	4	5	6	7	8	9	sum
1	1									1
2	1	1								2
3	2	3	1							6
4	6	11	6	1						24
5	24	50	35	10	1					120
6	120	274	225	85	15	1				720
7	720	1,764	1,624	735	175	21	1			5,040
8	5,040	13,068	13,132	6,769	1,960	322	28	1		40,320
9	40,320	109,584	118,124	67,284	22,449	4,536	546	36	1	362,880
	1	2	3	4	5	6	7	8	9	sum

Fixed points

The value f ( k , j ) counts the number of permutations of k elements with exactly j fixed points.

Properties

(1) For every j < 0 or j > k : f ( k , j ) = 0
.
(2) f ( 0 , 0 ) = 1
.
(3) For every k > 1 and k >= j >= 0 :
    f ( k , j ) = f ( k-1 , j-1 )
                + f ( k-1 , j   ) * ( k - 1 - j )
                + f ( k-1 , j+1 ) * ( j + 1 )

Reason of properties

(3) There are 3 different methods to construct a permutation of k elements with j fixed points:
(3.a) We may choose one of the f ( k-1 , j-1 ) permutations with k-1 elements and j-1 fixed points and add element k as a new fixed point.
(3.b) We may choose one of the f ( k-1 , j ) permutations with k-1 elements and j fixed points and insert element k in an existing circle of length > 1 in front of one of the (k-1) - j elements.
(3.c) We may choose one of the f ( k-1 , j+1 ) permutations with k-1 elements and j+1 fixed points and join element k with one of the j+1 fixed points to a circle of length 2.

Some values

k	j
	0	1	2	3	4	5	6	7	8	9	sum
1	0	1									1
2	1	0	1								2
3	2	3	0	1							6
4	9	8	6	0	1						24
5	44	45	20	10	0	1					120
6	265	264	135	40	15	0	1				720
7	1,854	1,855	924	315	70	21	0	1			5,040
8	14,833	14,832	7,420	2,464	630	112	28	0	1		40,320
9	133,496	133,497	66,744	22,260	5,544	1,134	168	36	0	1	362,880
	0	1	2	3	4	5	6	7	8	9	sum

Alternate calculations

$f(k,1)=\sum _{i=1}^{k}((-1)^{i+1}{k \choose i}i(k-i)!)$
Example: f ( 5 , 0 ) = 5*1*4! - 10*2*3! + 10*3*2! - 5*4*1! + 1*5*0! =
120 - 120 + 60 - 20 + 5 = 45

$f(k,0)=k!-\sum _{i=1}^{k}((-1)^{i+1}{k \choose i}(k-i)!)$
Example: f ( 5 , 1 ) = 120 - ( 5*4! - 10*3! + 10*2! - 5*1! + 1*0! ) =
120 - ( 120 - 60 + 20 - 5 + 1 ) = 120 - 76 = 44

For every k > 1:
$f(k,0)=(k-1)(f(k-1)+f(k-2))$
Example: f ( 5 , 0 ) = 4 * ( 9 + 2 ) = 4 * 11 = 44

For every k > 1:
$f(k,0)=n!\sum _{i=2}^{k}(((-1)^{i})/i!)$
Example: f ( 5 , 0 ) = 120 * ( 1/2 - 1/6 + 1/24 - 1/120 ) =
120 * ( 60/120 - 20/120 + 5/120 - 1/120 ) = 120 * 44/120 = 44

$f(k,0)\approx n!/e$ // ( e = Euler's number ~~ 2.71828 )
Example: f ( 5 , 0 ) ~~ 120 / e ~~ 44.14553

See also

• Cyclic permutation