Cycle index - Citizendia

In mathematics, and in particluar in the field of combinatorics, cycle indices are used in combinatorial enumeration when symmetries are to be taken into account. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Combinatorics is a branch of Pure mathematics concerning the study of discrete (and usually finite) objects Combinatorial enumeration is a subfield of Enumeration that deals with the counting of objects whose symmetries do not exist or if they exist are combinatorial in This is particularly important in species theory. This article is about a concept in combinatorial Mathematics.

Each permutation π of a finite set of objects partitions that set into cycles; the cycle index monomial of π is a monomial in variables a₁, a₂, … that describes the type of this partition (the cycle type of π): the exponent of a_i is the number of cycles of π of size i. In Mathematics, a partition of a set X is a division of X into non-overlapping " parts " or " blocks " Let S be a set A cycle is a Permutation ( bijective function of a set onto itself such that there exist distinct elements a_1 a_2\ldotsa_k In Mathematics, the word monomial means two different things in the context of Polynomials The first meaning is a product of powers of Variables The cycle index polynomial of a permutation group is the average of the cycle index monomials of its elements. In Mathematics, a permutation group is a group G whose elements are Permutations of a given set M, and whose group operation The terms cycle index and cycle indicator are also used, both for the cycle index monomial of a permutation and for the cycle index polynomial of a group.

Knowing the cycle index polynomial of a permutation group, one can enumerate equivalence classes of objects that arise when the group acts on a set of slots being filled with objects described by a generating function. In Mathematics a generating function is a Formal power series whose coefficients encode information about a Sequence a n This is the most common application and it uses the Pólya enumeration theorem. "Enumeration theorem" redirects here For its labelled counterpart see Labelled enumeration theorem.

1 Definition
2 Sample computations
3 Cycle indices of some groups
4 External links

Definition

The cycle index of a permutation group G is the average of

$a_1^{j_1(g)} a_2^{j_2(g)} a_3^{j_3(g)} \cdots$

over all permutations g of the group, where j_k(g) is the number of cycles of length k in the disjoint cycle decomposition of g.

More formally, let G be a permutation group of order m and degree n. Every permutation g in G has a unique decomposition into disjoint cycles, say c₁ c₂ c₃ . . . Let the length of a cycle c be denoted by |c|.

Now let j_k(g) be the number of cycles of g of length k, where

$0 \le j_k(g) \le \lfloor n/k \rfloor \mbox{ and } \sum_{k=1}^n k \, j_k(g) \; = n.$

We associate to g the monomial

$\prod_{c\in g} a_{|c|} = \prod_{k=1}^n a_k^{j_k(g)}$

in the variables a₁, a₂, . . . a_n.

Then the cycle index Z(G) of G is given by

$Z(G) = \frac{1}{|G|} \sum_{g\in G} \prod_{k=1}^n a_k^{j_k(g)}.$

The question of what the cycle structure of a random permutation looks like is an important question in the analysis of algorithms. An overview of the most important results may be found at random permutation statistics. The statistics of random permutations, such as the cycle structure of a Random permutation are of fundamental importance in the analysis of algorithms especially

Sample computations

Basic examples for disjoint cycle decompositions may be found here. In Mathematics, a permutation group is a group G whose elements are Permutations of a given set M, and whose group operation

The cyclic group C₃ contains the permutations

[1 2 3] = (1)(2)(3)
[2 3 1] = (1 2 3)
[3 1 2] = (1 3 2)

and its cycle index is

$Z(C_3) = \frac{1}{3} \left( a_1^3 + 2 a_3 \right).$

E. g. the factorization of g = [1 2 3] is (1)(2)(3), and g consists of three cycles of length one (fixed points), hence it is represented by a₁³.

The symmetric group S₃ contains the six permutations

[1 2 3] = (1)(2)(3)
[1 3 2] = (1)(2 3)
[2 1 3] = (1 2)(3)
[2 3 1] = (1 2 3)
[3 1 2] = (1 3 2)
[3 2 1] = (1 3)(2)

and its cycle index is

$Z(S_3) = \frac{1}{6} \left( a_1^3 + 3 a_1 a_2 + 2 a_3 \right).$

The cyclic group C₆ contains the six permutations

[1 2 3 4 5 6] = (1)(2)(3)(4)(5)(6)
[2 3 4 5 6 1] = (1 2 3 4 5 6)
[3 4 5 6 1 2] = (1 3 5)(2 4 6)
[4 5 6 1 2 3] = (1 4)(2 5)(3 6)
[5 6 1 2 3 4] = (1 5 3)(2 6 4)
[6 1 2 3 4 5] = (1 6 5 4 3 2).

and its cycle index is

$Z(C_6) = \frac{1}{6} \left( a_1^6 + a_2^3 + 2 a_3^2 + 2 a_6 \right).$

Case study: edge permutation group of graphs on three vertices

Consider graphs on three vertices. Every permutation in the group S₃ of vertex permutations induces an edge permutation and we want to compute the cycle index of the latter group. These are the permutations:

The identity.

No vertices are permuted, and no edges; the contribution is $a_1^3.\,$

Three reflections in an axis passing through a vertex and the midpoint of the opposite edge.

These fix one edge (the one not incident on the vertex) and exchange the remaining two; the contribution is $3 a_1 a_2.\,$

Two rotations, one clockwise, the other counterclockwise.

These create a cycle of three edges; the contribution is $2 a_3.\,$

The cycle index of the group G of edge permutations induced by vertex permutations from S₃ is

$Z(G) = \frac{1}{6} \left(a_1^3 + 3 a_1 a_2 + 2 a_3 \right)$

It happens that K₃ is its own dual and hence the edge permutation group induced by the vertex permutation group is the same as the vertex permutation group, namely S₃ and the cycle index is Z(S₃). This is not the case for graphs on more than three vertices, where the vertex permutation group has degree n and the edge permutation group has degree n(n − 1)/2. For n > 3 we have n(n − 1)/2 > n. We will see an example in the next section.

Case study: edge permutation group of graphs on four vertices

We compute the cycle index of the edge permutation group for graphs on four vertices. The process is entirely analogous to the three-vertex case. These are the vertex permutations and the edge permutations that they induce:

The identity.

This permutation maps all vertices (and hence, edges) to themselves and the contribution is $a_1^6.\,$

Six permutations that exchange two vertices.

These permutations preserve the edge that connects the two vertices as well as the edge that connects the two vertices not exchanged. The remaining edges form two two-cycles and the contribution is $6 a_1^2 a_2^2.\,$

Eight permutations that fix one vertex and produce a three-cycle for the three vertices not fixed.

These permutations create two three-cycles of edges, one containing those not incident on the vertex, and another one containing those incident on the vertex; the contribution is $8 a_3^2.\,$

Three permutations that exchange two vertex pairs at the same time.

These permutations preserve the two edges that connect the two pairs. The remaining edges form two two-cycles and the contribution is $3 a_1^2 a_2^2.\,$

Six permutations that rotate the vertices along a four-cycle.

These permutations create a four-cycle of edges (those that lie on the cycle) and exchange the remaining two edges; the contribution is $6 a_2 a_4.\,$

Note that we may visualize the types of permutations as symmetries of a regular tetrahedron. A regular Tetrahedron has 12 rotational (or orientation-preserving symmetries and a total of 24 symmetries including transformations that combine a reflection and a rotation This yields the following description of the permutation types.

The identity.
Reflection in the plane that contains one edge and the midpoint of the edge opposing it.
Rotation by 120 degrees about the axis passing through a vertex and the midpoint of the opposite face.
Rotation by 180 degrees about the axis connecting the midpoints of two opposite edges.
Six rotoreflections by 90 degrees.

We have computed the cycle index of the edge permuation group G of graphs on four vertices and it is

$Z(G) = \frac{1}{24} \left( a_1^6 + 9 a_1^2 a_2^2 + 8 a_3^2 + 6 a_2 a_4 \right).$

Case study: face permutations of a cube

Consider an ordinary cube in three-space and its automorphisms under rotations, which form a group, call it C. It permutes the six faces of the cube. (We could also consider edge permutations or vertex permutations. ) There are twenty-four automorphisms. We will classify them all and compute the cycle index of C.

The identity.

There is one such permutation and its contribution is $a_1^6.$

Six 90-degree face rotations.

We rotate about the axis passing through the centers of the face and the face opposing it. This will fix the face and the face opposing it and create a four-cycle of the faces parallel to the axis of rotation. The contribution is $6 a_1^2 a_4.$

Three 180-degree face rotations.

We rotate about the same axis as in the previous case, but now there is no four cycle of the faces parallel to the axis, but rather two two-cycles. The contribution is $3 a_1^2 a_2^2.$

Eight 120-degree vertex rotations.

This time we rotate about the axis passing through two opposite vertices (the endpoints of a main diagonal). This creates two three-cycles of faces (the faces incident on the same vertex form a cycle). The contribution is $8 a_3^2.$

Six 180-degree edge rotations.

These edge rotations rotate about the axis that passes through the midpoints of opposite edges not incident on the same face and parallel to each other and exchanges the two faces that are incident on the first edge, the two faces incident on the second edge, and the two faces that share two vertices but no edge with the two edges, i. e. there are three two-cycles and the contribution is $6 a_2^3.$

The conclusion is that the cycle index of the group C is

$Z(C) = \frac{1}{24} \left( a_1^6 + 6 a_1^2 a_4 + 3 a_1^2 a_2^2 + 8 a_3^2 + 6 a_2^3 \right) .$

Cycle indices of some groups

Identity group E_n

This group contains one permutation that fixes every element.

$Z(E_n) = a_1^n$

Cyclic group C_n

This is the group of rotations of n elements round a circle.

$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}$

Dihedral group D_n

Like the cyclic group, but also includes reflections.

$Z(D_n) = \frac{1}{2} Z(C_n) + \begin{cases} \frac{1}{2} a_1 a_2^{(n-1)/2}, & n \mbox{ odd, } \\ \frac{1}{4} \left( a_1^2 a_2^{(n-2)/2} + a_2^{n/2} \right), & n \mbox{ even.} \end{cases}$

The alternating group A_n

This group includes all even n! permutations of n elements.

$Z(A_n) = \sum_{j_1+2 j_2 + 3 j_3 + \ldots + k j_k = n} \frac{1 + (-1)^{j_2+j_4+\ldots}}{\prod_{k=1}^n k^{j_k} j_k!} \prod_{k=1}^n a_k^{j_k}$

The symmetric group S_n

This group includes all n! permutations of n elements.

$Z(S_n) = \sum_{j_1+2 j_2 + 3 j_3 + \ldots + k j_k = n} \frac{1}{\prod_{k=1}^n k^{j_k} j_k!} \prod_{k=1}^n a_k^{j_k}$

The formula for the cycle index is obtained by counting how many times a given permutation shape can occur. There are three steps: first partition the set of n labels into subsets, where there are $j k$ subsets of size k. Every such subset generates $k! / k$ cycles of length k. But we do not distinguish between cycles of the same size, i. e. they are permuted by $S_{j_k}$ . This yields

$\frac{n!}{\prod_{k=1}^n (k!)^{j_k}} \prod_{k=1}^n \left( \frac{k!}{k} \right)^{j_k} \prod_{k=1}^n \frac{1}{j_k!} = \frac{n!}{\prod_{k=1}^n k^{j_k} j_k!}.$

There is a useful recursive formula for the cycle index of the symmetric group. Set $Z (S 0) = 1$ and consider the size l of the cycle that contains n, where $\begin{matrix}1 \le l \le n.\end{matrix}$ There are $\begin{matrix}{n-1 \choose l-1}\end{matrix}$ ways to choose the remaining $l - 1$ elements of the cycle and every such choice generates $\begin{matrix}\frac{l!}{l}\end{matrix}$ different cycles.

This yields the recurrence

$Z(S_n) = \frac{1}{n!} \sum_{g\in S_n} \prod_{k=1}^n a_k^{j_k(g)} = \frac{1}{n!} \sum_{l=1}^n {n-1 \choose l-1} \; \frac{l!}{l} \; a_l \; (n-l)! \; Z(S_{n-l})$

$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l \; Z(S_{n-l}).$

External links

Marko Riedel, Pólya's enumeration theorem and the symbolic method.
Harald Fripertinger (1997). "Cycle indices of linear, affine and projective groups". Linear Algebra and Its Applications 263: 133–156. doi:10.1016/S0024-3795(96)00530-7. A digital object identifier ( DOI) is a permanent identifier given to an Electronic document.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Definition

Sample computations

Case study: edge permutation group of graphs on three vertices

Case study: edge permutation group of graphs on four vertices

Case study: face permutations of a cube

Cycle indices of some groups

Identity group En

Cyclic group Cn

Dihedral group Dn

The alternating group An

The symmetric group Sn

External links

Identity group E_n

Cyclic group C_n

Dihedral group D_n

The alternating group A_n

The symmetric group S_n