Cycles and fixed points

Cycles and fixed points
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 combinatorial 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 { c1, ..., cl }, such that

π(ci) = ci + 1 for i = 1, ..., l − 1, and π(cl) = c1.

The corresponding cycle of 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 l of the orbit is called the length of the corresponding cycle; when l = 1, the cycle is called a fixed point. 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 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

 \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 & 4 & 3 & 5 & 6 & 7 & 8 \\ 2 & 4 & 3 & 1 & 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 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 of S into orbits, and these are therefore the same for all such expressions. The cycle structure of a permutation is the partition of the size of S obtained by listing the lengths of the cycles (including a part 1 for each fixed point) in weakly decreasing order. The cycle structure of finite permutations is denoted by the elements of sequence OEISA198380.

Contents

Counting permutations by number of cycles

The unsigned Stirling number of the first kind, s(kj) counts the number of permutations of k elements with exactly j disjoint cycles.

Properties

(1) For every k > 0 : s(kk) = 1.
(2) For every k > 0 : s(k, 1) = (k − 1)!.
(3) For every k > j > 1, s(kj) = 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(kj) 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(kj) = 0.
(2) f(0, 0) = 1.
(3) For every k > 1 and kj ≥ 0, f(kj) = 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

f(k,1)=\sum_{i=1}^k(-1)^{i+1}{k \choose i}i(k-i)!

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.
f(k,0)=k!-\sum_{i=1}^k(-1)^{i+1}{k \choose i}(k-i)!

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:
f(k,0) = (k − 1)(f(k − 1,0) + f(k − 2,0))

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

For every k > 1:
f(k,0)=k!\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 k!/e
where e is Euler's number ≈ 2.71828

See also


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Fixed-gear bicycle — A fixed gear bicycle or fixed wheel bicycle, is a bicycle without the ability to coast. The sprocket is screwed directly on to the hub and there is no freewheel mechanism. A reverse thread lockring is usually fitted to prevent the sprocket from… …   Wikipedia

  • Automorphisms of the symmetric and alternating groups — In group theory, a branch of mathematics, the automorphisms and outer automorphisms of the symmetric groups and alternating groups are both standard examples of these automorphisms, and objects of study in their own right, particularly the… …   Wikipedia

  • Periodic points of complex quadratic mappings — This article describes periodic points of some complex quadratic map. This theory is applied in relation with the theories of Fatou and Julia sets.DefinitionsLet :f c(z)=z^2+c, where z and c are complex valued. (This f is the complex quadratic… …   Wikipedia

  • Exact sciences (The) in Hellenistic times: texts and issues — The exact sciences in Hellenistic times: Texts and issues1 Alan C.Bowen Modern scholars often rely on the history of Greco Latin science2 as a backdrop and support for interpreting past philosophical thought. Their warrant is the practice… …   History of philosophy

  • Dates and Dating — • In classical Latin even before the time of Christ it was usual for correspondents to indicate when and where their letters were written Catholic Encyclopedia. Kevin Knight. 2006. Dates and Dating     Dates and Dating …   Catholic encyclopedia

  • Mathematics and Physical Sciences — ▪ 2003 Introduction Mathematics       Mathematics in 2002 was marked by two discoveries in number theory. The first may have practical implications; the second satisfied a 150 year old curiosity.       Computer scientist Manindra Agrawal of the… …   Universalium

  • Pythagoreans and Eleatics — Edward Hussey PYTHAGORAS AND THE EARLY PYTHAGOREANS Pythagoras, a native of Samos, emigrated to southern Italy around 520, and seems to have established himself in the city of Croton. There he founded a society of people sharing his beliefs and… …   History of philosophy

  • Right- and left-hand traffic —   countries with right hand traffic …   Wikipedia

  • Milankovitch cycles — Past and future Milankovitch cycles. VSOP allows prediction of past and future orbital parameters with great accuracy. ε is obliquity (axial tilt). e is eccentricity. ϖ is longitude of perihelion. esin(ϖ) is the precession index, which together… …   Wikipedia

  • Bicycle and motorcycle dynamics — A computer generated, simplified model of bike and rider demonstrating an uncontrolled right turn. An …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”