Cycle index


In combinatorial mathematics a []cycle index is a polynomial in several variables which is structured in such a way that information about how a group of permutations acts on a set can be simply read off from the coefficients and exponents. This compact way of storing information in an algebraic form is frequently used in combinatorial enumeration.
Each permutation π of a finite set of objects partitions that set into cycles; the cycle index monomial of π is a monomial in variables a1, a2, … that describes the type of this partition : the exponent of ai 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 phrase cycle indicator is also sometimes used in place of cycle index.
Knowing the cycle index polynomial of a permutation group, one can enumerate equivalence classes due to the group's action. This is the main ingredient in the Pólya enumeration theorem. Performing formal algebraic and differential operations on these polynomials and then interpreting the results combinatorially lies at the core of species theory.

Permutation groups and group actions

A bijective map from a set X onto itself is called a permutation of X, and the set of all permutations of X forms a group under the composition of mappings, called the symmetric group of X, and denoted Sym. Every subgroup of Sym is called a permutation group of degree |X|. Let G be an abstract group with a group homomorphism φ from G into Sym. The image, φ, is a permutation group. The group homomorphism can be thought of as a means for permitting the group G to "act" on the set X. Such a group homomorphism is formally called a group action and the image of the homomorphism is a permutation representation of G. A given group can have many different permutation representations, corresponding to different actions.
Suppose that group G acts on set X. In combinatorial applications the interest is in the set X; for instance, counting things in X and knowing what structures might be left invariant by G. Little is lost by working with permutation groups in such a setting, so in these applications, when a group is considered, it is a permutation representation of the group which will be worked with, and thus, a group action must be specified. Algebraists, on the other hand, are more interested in the groups themselves and would be more concerned with the kernels of the group actions, which measure how much is lost in passing from the group to its permutation representation.

Disjoint cycle representation of permutations

Finite permutations are most often represented as group actions on the set X =. A permutation in this setting can be represented by a two line notation. Thus,
corresponds to a bijection on X = which sends 1 → 2, 2 → 3, 3 → 4, 4 → 5 and 5 → 1. This can be read off from the columns of the notation. When the top row is understood to be the elements of X in an appropriate order, only the second row need be written. In this one line notation, our example would be . This example is known as a cyclic permutation because it "cycles" the numbers around and a third notation for it would be. This cycle notation is to be read as: each element is sent to the element on its right, but the last element is sent to the first one. With cycle notation, it does not matter where a cycle starts, so and and all represent the same permutation. The length of a cycle is the number of elements in the cycle.
Not all permutations are cyclic permutations, but every permutation can be written as a product of disjoint cycles in essentially one way. As a permutation may have fixed points, these will be represented by cycles of length one. For example:
This permutation is the product of three cycles, one of length two, one of length three and a fixed point. The elements in these cycles are disjoint subsets of X and form a partition of X.
The cycle structure of a permutation can be coded as an algebraic monomial in several variables in the following way: a variable is needed for each distinct cycle length of the cycles that appear in the cycle decomposition of the permutation. In the previous example there were three different cycle lengths, so we will use three variables, a1, a2 and a3. The variable ai will be raised to the ji power where ji is the number of cycles of length i in the cycle decomposition of permutation g. We can then associate the cycle index monomial
to the permutation g. The cycle index monomial of our example would be a1a2a3, while the cycle index monomial of the permutation would be a13a22a42.

Definition

The cycle index of a permutation group G is the average of the cycle index monomials of all the permutations g in 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
c1 c2 c3....
Let the length of a cycle c be denoted by |c|.
Now let jk be the number of cycles of g of length k, where
We associate to g the monomial
in the variables a1, a2,..., an.
Then the cycle index Z of G is given by

Example

Consider the group G of rotational symmetries of a square in the Euclidean plane. Such symmetries are completely determined by the images of just the corners of the square. By labeling these corners 1, 2, 3 and 4 we can represent the elements of G as permutations of the set X =. The permutation representation of G consists of the four permutations,, and e = which represent the counter-clockwise rotations by 90°, 180°, 270° and 360° respectively. Notice that the identity permutation e is the only permutation with fixed points in this representation of G. As an abstract group, G is known as the cyclic group C4, and this permutation representation of it is its regular representation. The cycle index monomials are a4, a22, a4, and a14 respectively. Thus, the cycle index of this permutation group is:
The group C4 also acts on the unordered pairs of elements of X in a natural way. Any permutation g would send → . The set X is now where A =, B =, C =, D =, E = and F =. These elements can be thought of as the sides and diagonals of the square or, in a completely different setting, as the edges of the complete graph K4. Acting on this new set, the four group elements are now represented by,, and e = and the cycle index of this action is:
The group C4 can also act on the ordered pairs of elements of X in the same natural way. Any permutation g would send → . The elements of X could be thought of as the arcs of the complete digraph D4. The cycle index in this case would be:

Types of actions

As the above example shows, the cycle index depends on the group action and not on the abstract group. Since there are many permutation representations of an abstract group, it is useful to have some terminology to distinguish them.
When an abstract group is defined in terms of permutations, it is a permutation group and the group action is the identity homomorphism. This is referred to as the natural action.
The symmetric group S3 in its natural action has the elements
and so, its cycle index is:
A permutation group G on the set X is transitive if for every pair of elements x and y in X there is at least one g in G such that y = xg. A transitive permutation group is regular if the only permutation in the group that has fixed points is the identity permutation.
A finite transitive permutation group G on the set X is regular if and only if |G| = |X|. Cayley's theorem states that every abstract group has a regular permutation representation given by the group acting on itself by multiplication. This is called the regular representation of the group.
The cyclic group C6 in its regular representation contains the six permutations :
Thus its cycle index is:
Often, when an author does not wish to use the group action terminology, the permutation group involved is given a name which implies what the action is. The following three examples illustrate this point.

The cycle index of the ''edge permutation group'' of the complete graph on three vertices

We will identify the complete graph K3 with an equilateral triangle in the Euclidean plane. This permits us to use geometric language to describe the permutations involved as symmetries of the equilateral triangle. Every permutation in the group S3 of vertex permutations induces an edge permutation. These are the permutations:
The cycle index of the group G of edge permutations induced by vertex permutations from S3 is
It happens that the complete graph K3 is isomorphic to its own line graph and hence the edge permutation group induced by the vertex permutation group is the same as the vertex permutation group, namely S3 and the cycle index is Z. This is not the case for complete graphs on more than three vertices, since these have strictly more edges than vertices.

The cycle index of the edge permutation group of the complete graph on four vertices

This is entirely analogous to the three-vertex case. These are the vertex permutations and the edge permutations that they induce:
We may visualize the types of permutations geometrically as symmetries of a regular tetrahedron. This yields the following description of the permutation types.
The cycle index of the edge permutation group G of K4 is:

The cycle index of the face permutations of a cube

Consider an ordinary cube in three-space and its group of symmetries, call it C. It permutes the six faces of the cube.
There are twenty-four automorphisms.
The conclusion is that the cycle index of the group C is

Cycle indices of some permutation groups

Identity group ''E''''n''

This group contains one permutation that fixes every element.

Cyclic group ''C''n

A cyclic group, Cn is the group of rotations of a regular n-gon, that is, n elements equally spaced around a circle. This group has φ elements of order d for each divisor d of n, where φ is the Euler φ-function, giving the number of natural numbers less than d which are relatively prime to d. In the regular representation of Cn, a permutation of order d has n/d cycles of length d, thus:

Dihedral group ''D''n

The dihedral group is like the cyclic group, but also includes reflections. In its natural action,

Alternating group ''A''n

The cycle index of the alternating group in its natural action as a permutation group is
The numerator is 2 for the even permutations, and 0 for the odd permutations. The 2 is needed because

Symmetric group ''S''''n''

The cycle index of the symmetric group Sn in its natural action is given by the formula:
that can be also stated in terms of complete Bell polynomials:
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 subsets of size k. Every such subset generates cycles of length k. But we do not distinguish between cycles of the same size, i.e. they are permuted by. This yields
There is a useful recursive formula for the cycle index of the symmetric group.
Set and consider the size l of the cycle that contains n,
where
There are ways to choose the remaining elements of the cycle and every such choice generates
different cycles.
This yields the recurrence
or

Applications

Throughout this section we will modify the notation for cycle indices slightly by explicitly including the names of the variables. Thus, for the permutation group G we will now write:
Let G be a group acting on the set X. G also induces an action on the k-subsets of X and on the k-tuples of distinct elements of X, for 1 ≤ k ≤ n. Let fk and Fk denote the number of orbits of G in these actions respectively. By convention we set f0 = F0 = 1. We have:
a) The ordinary generating function for fk is given by:
b) The exponential generating function for Fk is given by:
Let G be a group acting on the set X and h a function from X to Y. For any g in G, h is also a function from X to Y. Thus, G induces an action on the set YX of all functions from X to Y. The number of orbits of this action is Z where b = |Y|.
This result follows from the orbit counting lemma and the weighted version of the result is Pólya's enumeration theorem.
The cycle index is a polynomial in several variables and the above results show that certain evaluations of this polynomial give combinatorially significant results. As polynomials they may also be formally added, subtracted, differentiated and integrated. The area of symbolic combinatorics provides combinatorial interpretations of the results of these formal operations.
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.