Английская Википедия:Cycles and fixed points
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
Permutation of four elements with 1 fixed point and 1 3-cycle
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 Шаблон:Math, such that
- Шаблон:Math for Шаблон:Math, and Шаблон:Math.
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 Шаблон:Mvar of the orbit is called the length of the corresponding cycle; when Шаблон:Math, 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
- <math> \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} </math>
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.[1] 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.
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]
Properties
- (1) For every k > 0 : Шаблон:Math
- (2) For every k > 0 : Шаблон:Math
- (3) For every k > j > 1, Шаблон:Math
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: Шаблон:Math
- (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 Шаблон:Math permutations with Шаблон:Math elements and Шаблон:Math 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 Шаблон:Math permutations with Шаблон:Math elements and j cycles and insert element k in an existing cycle in front of one of the Шаблон:Math elements.
Some values
| Шаблон:Mvar | Шаблон:Mvar | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 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 Шаблон:Math 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 : Шаблон:Math
- (2) f(0, 0) = 1.
- (3) For every k > 1 and k ≥ j ≥ 0, Шаблон:Math
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 Шаблон:Math permutations with Шаблон:Math elements and Шаблон:Math fixed points and add element k as a new fixed point.
- (3.b) We may choose one of the Шаблон:Math permutations with Шаблон:Math elements and j fixed points and insert element k in an existing cycle of length > 1 in front of one of the Шаблон:Math elements.
- (3.c) We may choose one of the Шаблон:Math permutations with Шаблон:Math elements and Шаблон:Math fixed points and join element k with one of the Шаблон:Math fixed points to a cycle of length 2.
Some values
| Шаблон:Mvar | Шаблон:Mvar | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 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
| Equations | Examples |
|---|---|
| <math>f(k,1)=\sum_{i=1}^k(-1)^{i+1}{k \choose i}i(k-i)!</math> | <math>\begin{align}
f(5, 1) &= 5\times 1 \times4! - 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{align}</math> |
| <math>f(k,0)=k!-\sum_{i=1}^k(-1)^{i+1}{k \choose i}(k-i)!</math> | <math>\begin{align}
f(5, 0) &= 120 - ( 5\times4! - 10\times3! + 10\times2! - 5\times1! + 1\times0! ) \\ &= 120 - ( 120 - 60 + 20 - 5 + 1 ) = 120 - 76 = 44. \end{align}</math> |
For every k > 1:
|
<math>f(5, 0) = 4 \times ( 9 + 2 ) = 4 \times 11 = 44</math> |
For every k > 1:
|
<math>\begin{align}
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{align}</math> |
<math>f(k,0)\approx \frac{k!}e</math>
|
See also
Notes
References
