In combinatorial

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

 mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the cycles of a permutation

Permutation

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

 π of a finite set S correspond bijectively to the orbits of the subgroup generated by π acting on S. These orbits are subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of S that can be written as { c₁, ..., c_l }, such that

π(c_i) = c_{i + 1} for i = 1, ..., l − 1, and π(c_l) = 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 l of the orbit is called the length of the corresponding cycle; when l = 1, the cycle is called a fixed point

Fixed point (mathematics)

In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...

. In counting the fixed points among the cycles of a permutation, the combinatorial notion of cycle differs from the group theoretical one, where a cycle

Cycle (mathematics)

In mathematics, and in particular in group theory, a cycle is a permutation of the elements of some set X which maps the elements of some subset S to each other in a cyclic fashion, while fixing all other elements...

 is a permutation in itself, and its length cannot be 1 (even if that were allowed, this would not suffice to distinguish different fixed points, since any cycle of length 1 would be equal to the identity 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

π = ( 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 an 7 are fixed points of π, since π(5)=5 and π(7)=7. This kind of expression resembles the group-theoretic decomposition of a permutation as a product of cycles with disjoint orbits, but in that decomposition the fixed points do not appear.

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

Partition of a set

In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...

 of S into orbits, and these are therefore the same for all such expressions.

Counting permutations by number of cycles

The unsigned Stirling number

Stirling number

In mathematics, Stirling numbers arise in a variety of combinatorics problems. They are named after James Stirling, who introduced them in the 18th century. Two different sets of numbers bear this name: the Stirling numbers of the first kind and the Stirling numbers of the second...

 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)!.

(3) For every k > j > 1, s(k, j) = s(k − 1,j − 1) + s(k − 1, j)·(k − 1)

Reasons for properties

(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. ( 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 two different ways 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 cycles and add element k as a new cycle of length 1.

(3.b) If we want element k not to be a fixed point we may choose one of the s(k − 1, j ) permutations with k − 1 elements and j cycles and insert element k in an existing cycle 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

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.

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)

Reasons for properties

(3) There are three 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 cycle 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 cycle 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

Example: f(5, 1) = 5×1×4! − 10×2×3! + 10×3×2! - 5×4×1! + 1×5×0!

= 120 - 120 + 60 - 20 + 5 = 45.

Example: f(5, 0) = 120 - ( 5×4! - 10×3! + 10×2! - 5×1! + 1×0! )

= 120 - ( 120 - 60 + 20 - 5 + 1 ) = 120 - 76 = 44.

For every k > 1:

Example: f(5, 0) = 4 × ( 9 + 2 ) = 4 × 11 = 44

For every k > 1:

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

where e is Euler's number

E (mathematical constant)

The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...

≈ 2.71828