Cycle type

The cycle type , or type for short , is an important property of permutations in combinatorics and group theory . The cycle type describes the number and length of the cycles in the cycle representation of a permutation. The number of possible type -digit permutations corresponds to the number of partitions of the number . The number of permutations per cycle type can be calculated from the type description, with the permutations with the same number of cycles being counted by the Stirling numbers of the first type. ${\displaystyle n}$ ${\displaystyle n}$

The inverse permutation always has the type of the initial permutation . The result of the composition of two permutations always has the same cycle type, regardless of the order of the operands. Furthermore, two permutations are conjugated to one another if and only if they are of the same type. The permutations of the same cycle type thus form the conjugation classes of the symmetrical group of degree . ${\displaystyle n}$

definition

Each permutation of the symmetrical group can be unambiguously represented (except for interchanging the factors) as a composition of at most pair-wise disjoint cycles . If now denotes the length of a permutation for the number of cycles , then the cycle type of this permutation is the formal expression ${\displaystyle S_{n}}$ ${\displaystyle n}$ ${\displaystyle b_{j}}$ ${\displaystyle j=1,\ldots ,n}$ ${\displaystyle j}$ ${\displaystyle \pi \in S_{n}}$

${\displaystyle \operatorname {typ} (\pi )=1^{b_{1}}2^{b_{2}}\ldots n^{b_{n}}}$,

whereby the terms do not have to be listed with. Formal here means that the product and the potencies are not actually calculated. Sometimes the expression is also provided with square brackets . An alternative representation of the type of a permutation is the tuple ${\displaystyle b_{j}=0}$ ${\displaystyle s}$

${\displaystyle \operatorname {typ} (\pi )=\left(k_{1},k_{2},\ldots ,k_{s}\right)}$,

where and are the lengths of the cycles in the cycle representation of the permutation in descending order. Occasionally the cycle lengths are also noted in ascending order. Both representations contain the same information about a permutation and can easily be converted into one another. ${\displaystyle s\leq n}$ ${\displaystyle k_{1}\geq \ldots \geq k_{s}\in \mathbb {N} }$

Examples

Concrete examples

Graph of a permutation of type or . ${\displaystyle 1^{1}2^{1}4^{1}}$ ${\displaystyle (4,2,1)}$

The permutation

${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5&6&7\\2&4&1&3&5&7&6\end{pmatrix}}=(1243)(5)(67)\in S_{7}}$

indicates the cycle type

${\displaystyle \operatorname {typ} (\pi )=1^{1}2^{1}3^{0}4^{1}5^{0}6^{0}7^{0}=1^{1}2^{1}4^{1}}$   or   ${\displaystyle \operatorname {typ} (\pi )=\left(4,2,1\right)}$

because their cycle representation consists of one cycle each of length one, two and four. The same cycle type also has the permutation . ${\displaystyle \pi =(1457)(36)(2)\in S_{7}}$

More general examples

The following types of digit permutations with each have the associated cycle type: ${\displaystyle n}$ ${\displaystyle \pi \in S_{n}}$ ${\displaystyle n\geq 2}$

• identical permutation :

${\displaystyle \operatorname {typ} (\pi )=1^{n}}$   or   ${\displaystyle \operatorname {typ} (\pi )=(1,\ldots ,1)}$

• Transpositions (exchanges):

${\displaystyle \operatorname {typ} (\pi )=1^{n-2}2^{1}}$   or   ${\displaystyle \operatorname {typ} (\pi )=(2,1,\ldots ,1)}$

• cyclic permutations of length : ${\displaystyle r\geq 2}$

${\displaystyle \operatorname {typ} (\pi )=1^{n-r}r^{1}}$   or   ${\displaystyle \operatorname {typ} (\pi )=(r,1,\ldots ,1)}$

• Fixed point free permutations :

${\displaystyle \operatorname {typ} (\pi )=2^{b_{2}}\ldots n^{b_{n}}}$   or   with for everyone ${\displaystyle \operatorname {typ} (\pi )=\left(k_{1},\ldots ,k_{s}\right)}$ ${\displaystyle k_{j}\geq 2}$ ${\displaystyle j}$

• self-inverse permutations :

${\displaystyle \operatorname {typ} (\pi )=1^{b_{1}}2^{b_{2}}}$   or   with for everyone ${\displaystyle \operatorname {typ} (\pi )=\left(k_{1},\ldots ,k_{s}\right)}$ ${\displaystyle k_{j}\leq 2}$ ${\displaystyle j}$

Numbers

${\displaystyle n}$	Cycle type		Cycle structure	number
1	1 1	(1)	(•)	1
2	1 2	(1.1)	(•) (•)	1
	2 1	(2)	(• •)	1
3	1 3	(1,1,1)	(•) (•) (•)	1
	1 1 2 1	(2.1)	(• •) (•)	3
	3 1	(3)	(• • •)	2
4th	1 4	(1,1,1,1)	(•) (•) (•) (•)	1
	1 2 2 1	(2,1,1)	(• •) (•) (•)	6th
	2 2	(2.2)	(• •) (• •)	3
	1 1 3 1	(3.1)	(• • •) (•)	8th
	4 1	(4)	(• • • •)	6th
5	1 5	(1,1,1,1,1)	(•) (•) (•) (•) (•)	1
	1 3 2 1	(2,1,1,1)	(• •) (•) (•) (•)	10
	1 1 2 2	(2.2.1)	(• •) (• •) (•)	15th
	1 2 3 1	(3.1.1)	(• • •) (•) (•)	20th
	2 1 3 1	(3.2)	(• • •) (• •)	20th
	1 1 4 1	(4.1)	(• • • •) (•)	30th
	5 1	(5)	(• • • • •)	24

Number of types

The following always applies to the number and length of the cycles of a -digit permutation ${\displaystyle n}$

${\displaystyle 1\cdot b_{1}+2\cdot b_{2}+\ldots +n\cdot b_{n}=n}$,

therefore some of the numbers must be zero. The same applies to the sum of all cycle lengths ${\displaystyle n\geq 2}$ ${\displaystyle b_{j}}$

${\displaystyle k_{1}+k_{2}+\ldots +k_{s}=n}$.

Therefore, the number of Zykeltypen in corresponds precisely to the number of partitions of the number by the result ${\displaystyle S_{n}}$ ${\displaystyle n}$

${\displaystyle 1,2,3,5,7,11,\ldots }$   (Follow A000041 in OEIS )

given is. The table on the right shows the number of cycle types in the number of lines for the given . ${\displaystyle S_{n}}$ ${\displaystyle n}$

Number of permutations per type

The number of permutations with is ${\displaystyle \pi \in S_{n}}$ ${\displaystyle \operatorname {typ} (\pi )=1^{b_{1}}2^{b_{2}}\ldots n^{b_{n}}}$

${\displaystyle {\frac {n!}{b_{1}!\cdot b_{2}!\cdot \ldots \cdot b_{n}!\cdot 1^{b_{1}}\cdot 2^{b_{2}}\cdot \ldots \cdot n^{b_{n}}}}}$   (Follow A036039 in OEIS ),

for the cycles of length can be arranged in different ways, and each of these cycles can be written in different ways. These numbers can be found in the last column of the adjacent table. With the help of the tuple representation, the number of possible permutations of a given cycle type can also be determined ${\displaystyle j}$ ${\displaystyle b_{j}!}$ ${\displaystyle j}$

${\displaystyle {\frac {n!}{b_{1}!\cdot \ldots \cdot b_{n}!\cdot k_{1}\cdot \ldots \cdot k_{s}}}}$,

specify. Related to this are the Stirling numbers of the first kind , which indicate the number of -digit permutations that have exactly cycles. The Stirling numbers result from the sum of the numbers of permutations with the same number of cycles. For example, the Stirling number , see the second and third from last line in the table. ${\displaystyle s_{n,k}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle s_{5,2}=30+20=50}$

Cycle classes

The permutations of the same cycle type form equivalence classes and one writes when two permutations have the same type, that is ${\displaystyle \pi \sim \sigma }$ ${\displaystyle \pi ,\sigma \in S_{n}}$

${\displaystyle \pi \sim \sigma \Leftrightarrow \operatorname {typ} (\pi )=\operatorname {typ} (\sigma )}$.

The following always applies to the inverse permutation of a permutation ${\displaystyle \pi ^{-1}}$ ${\displaystyle \pi }$

${\displaystyle \pi ^{-1}\sim \pi }$,

because the inversion only reverses the order of the numbers within the individual cycles. In general, executing two permutations one after the other is not commutative , but it always holds ${\displaystyle \pi ,\sigma }$

${\displaystyle \pi \circ \sigma \sim \sigma \circ \pi }$,

the result of a composition therefore has the same cycle type regardless of the order of the operands. Even conjugation with any permutation does not change the type of a permutation , that is, it holds ${\displaystyle \sigma }$ ${\displaystyle \pi }$

${\displaystyle \sigma \circ \pi \circ \sigma ^{-1}\sim \pi }$.

In general, two permutations are conjugated if and only if they are of the same type. The -digit permutations of the same cycle type therefore form the conjugation classes of the symmetric group . ${\displaystyle n}$ ${\displaystyle S_{n}}$

See also

• Young tableau
• Cycle hand

literature

• Martin Aigner : Discrete Mathematics . Vieweg, 2006, ISBN 3-8348-9039-1 .
• Michael Artin : Algebra . Springer, 1998, ISBN 3-7643-5938-2 .
• Konrad Jacobs , Dieter Jungnickel : Introduction to combinatorics . de Gruyter, 2003, ISBN 3-11-016727-1 .
• Hans Kurzweil, Bernd Stellmacher : Theory of finite groups: an introduction . Springer, 1998, ISBN 3-540-60331-X .
• Kristina Reiss , Gernot Stroth : Finite Structures . Springer, 2011, ISBN 3-642-17181-8 .

Web links

• Roger Lipsett: Conjugacy classes in the symmetric group S ⁿ . In: PlanetMath . (English)

Individual evidence

1. ↑ ^{a b} Aigner: Discrete Mathematics . S. 11 .
2. ↑ Reiss, Stroth: Finite structures . S. 171 .
3. ^ Artin: Algebra . S. 241 .
4. ↑ ^{a b c} Kurzweil, Stellmacher: Theory of finite groups: an introduction . S. 80 .
5. ^ Jacobs, Jungnickel: Introduction to combinatorics . S. 293 .
6. ↑ ^{a b} Aigner: Discrete Mathematics . S. 12 .
7. ^ Artin: Algebra . S. 242 .