Cyclic permutation

from Wikipedia, the free encyclopedia
Graph of a cyclic permutation of numbers from 1 to 8

A cyclic permutation , or cycle for short (from the Greek κύκλος 'circle' ), is a permutation in combinatorics and group theory that swaps certain elements of a set in a circle and holds the others. The first element of the cycle is mapped onto the second, the second element onto the third, and so on up to the last element, which is mapped back onto the first.

Cyclic permutations have a number of special properties. The concatenation of two cyclic permutations is commutative if they have disjoint carriers. The inverse permutation of a cyclic permutation is always cyclic as well. Furthermore, any powers of a cyclic permutation, the length of which is a prime number , again result in cyclic permutations. The cyclic permutations of fixed length also form conjugation classes of the symmetric group of all permutations.

Every cyclic permutation can be broken down into individual transpositions and therefore has an even sign if and only if its length is odd. Each permutation can in turn be written as a concatenation of pairwise disjoint cycles, which is used in the cycle notation of permutations. The order of a permutation then corresponds to the least common multiple of the lengths of these cycles. Cyclic permutations with long cycle lengths play an important role in the construction of pseudorandom number generators .


If the symmetric group of all permutations of the set is , then a permutation is called cyclic with length or cycle if it interchanges a list of pairwise different numbers in a circle, that is


and holds all other numbers. So it must apply


such as

  for   .

The amount is called the carrier or path of . In a more general way, permutations of any finite sets , for example alphabets , can be considered, but the analysis of the mathematical properties can be limited to the first natural numbers.


In addition to the above function notation , in which the figure is specified in full, a cyclic permutation can also be noted by using only the numbers that are cyclically exchanged as indices using

can be specified. Often a cyclic permutation is also noted in cycle notation by putting these numbers in brackets without separators:

Both spellings assume that the total number of numbers is known. The index and cycle notation are not clear, however, because the starting number can be selected as desired within the cycle. Each cycle can do so in different ways


to be discribed. However, the convention that is often set is to choose the smallest or the largest number of the cycle.


Cyclic permutations in S 4
length Cyclic permutations number
1 id 1
2 (1 2), (1 3), (1 4),
(2 3), (2 4), (3 4)
3 (1 2 3), (1 2 4), (1 3 2), (1 3 4),
(1 4 2), (1 4 3), (2 3 4), (2 4 3)
4th (1 2 3 4), (1 2 4 3), (1 3 2 4),
(1 3 4 2), (1 4 2 3), (1 4 3 2)

Is a simple cyclic permutation of length three


Here, the number is the number , the number of the number and the number back on the number displayed. The permutation

is a cyclic permutation of length two in which the numbers and are swapped and the numbers and are retained. Any cyclic permutation of length one

corresponds exactly to the identical permutation , which leaves all numbers unchanged. The cyclic permutations listed in the adjacent table are found in the symmetric group . Of the permutations in , only three permutations are therefore non-cyclic, namely those that exchange two pairs of numbers.

Special cases

The following special cases are considered for cyclic permutations:

Exchange or transposition
A cyclic permutation that swaps exactly two elements with one another, i.e.
  for   .
Neighbor swap or neighboring transposition
A cyclic permutation that interchanges two successive elements, i.e.
  for   .
Cyclic shift to the right
A cyclic permutation that swaps all elements in ascending order in a circle, i.e.
Cyclic left shift
A cyclic permutation that swaps all elements in a circle in descending order, i.e.



Number of k cycles in S n
1 2 3 4th 5 6th total
1 1 1
2 1 1 2
3 1 3 2 6th
4th 1 6th 8th 6th 21st
5 1 10 20th 30th 24 85
6th 1 15th 40 90 144 120 410

In the set of the various permutations of the numbers there are exactly many cycles. Each permutation in tuple notation corresponds to a cycle , which in turn can be written in different ways. If now generally denotes the set of -cycles in , then applies to

   (Follow A111492 in OEIS ),

because there are ways to choose from numbers. For the total amount of all cyclic permutations including the identical permutation, the following applies:

   (Follow A121726 in OEIS )


In general, the sequential execution of two cyclic permutations is not commutative . However , if they have two cyclic permutations and disjoint carriers, the following applies


then their order can be reversed when they are executed one after the other, that is, it applies


Cyclic permutations with disjoint carriers are also called disjoint cycles.

Isolation and Inverse

Executing two cyclic permutations one after the other is not necessarily cyclic again, like the example

shows. Therefore, the amount of the cyclic permutations forms for any subgroup of the symmetric group . However, the inverse permutation of a cyclic permutation is always also a cyclic permutation, namely the one that cyclically interchanges the numbers in the reverse order, that is


The inverse permutation of a transposition is thus the same transposition again.


Move is a cyclic permutation applied twice in succession, all the indices cyclically , that is, is set to ready, on and so on until the on and on . In general, by applying a cyclic permutation one time, all indices are shifted cyclically . The -th power of a cyclic permutation of the length is itself cyclic again if and only if and are coprime . In particular, the repeated application of a cyclic permutation results in the identical permutation, i.e.


and the repeated application results in the initial permutation, that is


Hence the crowd forms

with the sequential execution of a subset of the symmetric group , wherein the inverse element to be. This subgroup is isomorphic to the cyclic group and consists exclusively of cyclic permutations if and only if is a prime number .


For a cyclic permutation

which is calculated conjugation with an arbitrary permutation to


so it again results in a cycle. The set forms a conjugation class for each group . In general, two permutations are conjugated to each other if and only if their cycle type matches.


Breakdown of cycles into sub-cycles

Every cyclic permutation of the length can be changed at any point using

break it down into two sub-cycles. If this decomposition is applied repeatedly , it results that every cyclic permutation of the length is by means of

can be written as a chain of transpositions. For the sign of a cyclic permutation of the length, the following applies


since transpositions always have an odd sign. A cyclic permutation is even if and only if its length is odd.


The cyclic permutation of length four can be passed through

split into three transpositions and is therefore odd.

Decomposition of permutations into cycles

Graph of a permutation of the numbers from 1 to 7, which breaks down into three disjoint cycles

Each permutation can be clearly represented (except for the interchanging of the factors) as a concatenation of pairs of disjoint cycles. That is, it applies

with pairwise disjoint carriers for , where is. The Stirling numbers of the first kind indicate how many permutations can be written in as a concatenation of exactly cyclic permutations. The order of a permutation corresponds to the order of the associated cyclic group and is therefore the smallest common multiple of the lengths of these cycles. Furthermore, the sign of a permutation results from the number of cycles of even length.


The permutation

breaks down into the three disjoint cycles

and thus has the order . Since only one of the three cycles is even in length, the permutation is odd.


Cyclic permutations with long cycle lengths play an important role in the construction of pseudorandom number generators . The maximum period of such a random number generator corresponds to the number of possible states of the generator. With simple recursive generators of the form

with the number of possible states is even . The period of such a generator is then maximal if the function represents a cyclic permutation of the length of the set . In the case of linear congruence generators of the type

Knuth's theorem provides sufficient and necessary conditions for the parameters and for the maximality of the period length.


Web links