Cycle hand

The cycle pointer , also called cycle indicator , is used in mathematics as an aid when symmetries can be taken into account when determining more complex numbers in combinatorics .

Specifically, the cycle pointer is a polynomial which abstracts information about the structure of a suitable group .

The best-known application is Pólya's theorem , which enables more complex equivalence classes of objects to be counted, such as the number of all genuinely different molecules in a family in chemistry or that of trees in graph theory .

Formal definition

Let be a permutation group with elements of degree . Each permutation can be clearly represented as a union of disjoint cycles . The cycle type of the permutation is given by the number of all cycles of with length , thus ${\displaystyle G}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \sigma \in G}$ ${\displaystyle j_{k}(\sigma )}$ ${\displaystyle \sigma }$ ${\displaystyle k}$

${\displaystyle 0\leq j_{k}(\sigma )\leq \lfloor n/k\rfloor {\text{ und }}\sum _{k=1}^{n}k\,j_{k}(\sigma )\;=n.}$

Now everyone becomes a monom ${\displaystyle \sigma \in G}$

${\displaystyle M(\sigma ):=a_{1}^{j_{1}(\sigma )}\cdot a_{2}^{j_{2}(\sigma )}\cdot \cdots \cdot a_{n}^{j_{n}(\sigma )}=\prod _{k=1}^{n}a_{k}^{j_{k}(\sigma )}}$

assigned in the variables . Then the cycle pointer of is given by the polynomial forming the average ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$ ${\displaystyle G}$

${\displaystyle Z(G):=Z(G;a_{1},a_{2},\ldots a_{n}):={\frac {1}{|G|}}\sum _{\sigma \in G}M(\sigma )={\frac {1}{m}}\sum _{\sigma \in G}\prod _{k=1}^{n}a_{k}^{j_{k}(\sigma )}}$.

Examples

Cyclical group ${\displaystyle C_{3}}$

The cyclic group is made up of the three permutations ${\displaystyle C_{3}=\lbrace a^{0},\,a^{1},\,a^{2}\rbrace }$

${\displaystyle {\begin{aligned}a^{0}=\sigma _{1}=[123]&=(1)(2)(3)\\a^{1}=\sigma _{2}=[231]&=(123)\\a^{2}=\sigma _{3}=[312]&=(132)\end{aligned}}}$

realized . consists of cycles of length one, so the corresponding monomial is . In contrast, and each consist of a cycle of length 3, so the monomial results twice . Averaging leads to the cycle pointer of : ${\displaystyle \sigma _{1}}$ ${\displaystyle 3}$ ${\displaystyle a_{1}^{3}}$ ${\displaystyle \sigma _{2}}$ ${\displaystyle \sigma _{3}}$ ${\displaystyle a_{3}^{1}}$ ${\displaystyle C_{3}}$

${\displaystyle Z(C_{3})={\frac {1}{3}}\left(a_{1}^{3}+2a_{3}\right)}$.

Symmetrical group ${\displaystyle S_{3}}$

The symmetric group consists of the six permutations ${\displaystyle S_{3}}$

${\displaystyle {\begin{aligned}\sigma _{1}=[123]&=(1)(2)(3)\\\sigma _{2}=[132]&=(1)(23)\\\sigma _{3}=[213]&=(12)(3)\\\sigma _{4}=[231]&=(123)\\\sigma _{5}=[312]&=(132)\\\sigma _{6}=[321]&=(13)(2)\end{aligned}}}$

and the cycle hand is

${\displaystyle Z(S_{3})={\frac {1}{6}}\left(a_{1}^{3}+3a_{1}a_{2}+2a_{3}\right)}$.

Rotary group of a cube

Cube with colored sides

The rotation group of a cube , i.e. the automorphism group of its rotations in three-dimensional space, can be represented as a permutation group of the six sides of the cube. There are a total of 24 different automorphisms that have to be classified for the calculation of the cycle indicator of this group: ${\displaystyle G}$

• A rotation of 0 °: This is the identity that the monomial contributes. ${\displaystyle a_{1}^{6}}$

• Six rotations of the sides by 90 °: There are three possibilities to put the axis of rotation through the center of one side and the one on the opposite side. These two sides remain unchanged by the rotation, whereas the other four sides are each permuted by a cycle of length 4 parallel to the axis of rotation. This gives the monom . ${\displaystyle 3\cdot 2\cdot a_{1}^{2}a_{4}}$

• Three rotations of the pages by 180 °: It is rotated around the same axis as just above. This time, however, opposite sides are swapped, so that two cycles of length 2 arise. This gives the monom . ${\displaystyle 3\cdot a_{1}^{2}a_{2}^{2}}$

• Eight rotations of the corners by 120 °: The four axes of rotation go through two opposite points, i.e. H. the endpoints of a main diagonal. There are two cycles of the length 3 of the surfaces that adjoin the end points. This gives the monom . ${\displaystyle 4\cdot 2\cdot a_{3}^{2}}$

• Six rotations of the edges by 180 °: The axis of rotation goes through the centers of two diagonally opposite edges. The two sides that adjoin one of the two edges are swapped, as well as the two sides that only adjoin one corner of the two edges. In total there are three cycles of length 2 and the result is the monomial . ${\displaystyle 6\cdot a_{2}^{3}}$

Overall, this results for the cycle pointer of group G

${\displaystyle Z(G)={\frac {1}{24}}\left(a_{1}^{6}+6a_{1}^{2}a_{4}+3a_{1}^{2}a_{2}^{2}+8a_{3}^{2}+6a_{2}^{3}\right).}$

This formula can now be used for various combinatorial problems: The substitution and application of Pólya's theorem gives roughly that it is a total ${\displaystyle a_{1}:=a_{2}:=a_{3}:=a_{4}:=n}$

${\displaystyle {\frac {1}{24}}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right)}$

There are really different (i.e. not interconvertible by rotation) ways of coloring the sides of a cube with different colors . ${\displaystyle n}$

Note : Alternatively, one could have looked at a group acting on the corners or edges (if the cube is interpreted as a graph ), which, however, would lead to other cycle pointers.

Web links

• Nicolaas Govert de Bruijn : Pólya's counting theory: patterns for graphs and chemical compounds . (PDF; 1 MB; 26 pages) - A detailed and readable introduction in which the evidence is motivated by concrete examples. Also published in: Konrad Jacobs (Ed.): Selecta Mathematica III . Springer, Berlin 1971, ISBN 3-540-05333-6 (Heidelberg paperbacks).
• William May: Introduction to Pólya Enumeration Theory . (PDF; 1.4 MB; 41 slides)
• Harald Fripertinger: Cycle pointer of linear groups and counting of linear codes . (PDF; 180 kB; 13 pages)
• Marko Riedel: Pólya's enumeration theorem and the symbolic method . (PDF; 181 kB; 14 pages) - Contains in particular formulas for cycle pointers of several elementary groups.

literature

• Martin Aigner: Discrete Mathematics . Chapter 4.4 Pattern and cycle indicator . 6. corr. Ed. Vieweg + Teubner, 2006, ISBN 978-3-8348-0084-8 .
• Konrad Jacobs, Dieter Jungnickel: Introduction to combinatorics . de Gruyter textbook, 2003, ISBN 978-3-11-019799-0 , Chapter XIII The counting theory of Pólya .