Cycle index

In mathematics, and in particular in the field of combinatorics, cycle indices are used in combinatorial enumeration when symmetries are to be taken into account. This is particularly important in species theory.

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. The cycle index polynomial of a permutation group is the average of the cycle index monomials of its elements. 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. This is the most common application and it uses the Pólya enumeration theorem.

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.

Examples

Basic examples of disjoint cycle decompositions may be found here.

The cyclic group C₃ = {e,(1 2 3),(1 3 2)} consists of the identity and two 3-cycles. Thus its cycle index is

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

The symmetric group S₃ has the elements

S₃ = {e,(23),(12),(123),(132),(13)}

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. 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

Cube with colored faces

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

Cyclic group 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}$

This formula is easily verified for powers of primes n = p^v, where we use the fact that the cyclic group is isomorphic to the group generated by g = exp 2πi / n with multiplication being the group operation. It is thus readily apparent that the order of g^k is LCM(k,n) / k or n / GCD(n,k). The possible values of the order are $1, p, p^2, p^3, \ldots, p^v$ according to whether $GCD(n, k) = p^v, p^{v-1}, p^{v-2}, \ldots, 1.$ But the number of solutions from the interval [1,n] to GCD(n,k) = p^{v − w} is one when w = 0 and p^w − p^{w − 1} otherwise, so that the number of elements of each order is $1, p-1, p^2-p, \ldots, p^v-p^{v-1}$, giving

$Z(C_n) = \frac{1}{p^v} \sum_{w=0}^v \varphi(p^w) a_{p^w}^{p^{v-w}}$

which is the formula from above (where we have taken into account that a permutation of order p^w splits into p^{v − w} cycles, each of which is obtained by a single application of g).

Dihedral group D_n

Dihedral group is 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

The alternating group includes all even n! permutations of n elements.

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

The symmetric group S_n

The cycle index of the symmetric group S_n is given by the formula:

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

that can be also stated in terms of complete Bell polynomials:

$Z(S_n) = \frac{B_n(0!\,a_1, 1!\,a_2, \dots, (n-1)!\,a_n)}{n!}.$

This formula 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₀) = 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})$

or

$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. http://www.uni-graz.at/~fripert/linaffproj.html.