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.

Performing formal algebraic and differential operations on these polynomials and then interpreting the results combinatorially lies at the core of species theory.

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(X ).

Every subgroup of Sym(X ) is called a permutation group of degree |X |.

[3] Finite permutations are most often represented as group actions on the set X = {1,2, ..., n}.

[4] This example is known as a cyclic permutation because it "cycles" the numbers around, and a third notation for it would be (1 2 3 4 5).

The elements in these cycles are disjoint subsets of X and form a partition of X.

Now let jk(g) 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(G) of G is given by Consider the group G of rotational symmetries of a square in the Euclidean plane.

Its elements are completely determined by the images of just the corners of the square.

By labeling these corners 1, 2, 3 and 4 (consecutively going clockwise, say) we can represent the elements of G as permutations of the set X = {1,2,3,4}.

Acting on this new set, the four group elements are now represented by (A D C B)(E F), (A C)(B D)(E)(F), (A B C D)(E F) and e = (A)(B)(C)(D)(E)(F), 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 (x,y) → (x g, y g) (in this case we would also have ordered pairs of the form (x, x)).

The elements of X could be thought of as the arcs of the complete digraph D4 (with loops at each vertex).

Since there are many permutation representations of an abstract group, it is useful to have some terminology to distinguish them.

A finite transitive permutation group G on the set X is regular if and only if |G| = |X |.

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

This is not the case for complete graphs on more than three vertices, since these have strictly more edges (

The cycle index of the edge permutation group G of K4 is: Consider an ordinary cube in three-space and its group of symmetries, call it C. It permutes the six faces of the cube.

This group has φ(d ) elements of order d for each divisor d of n, where φ(d ) 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:[12] The dihedral group is like the cyclic group, but also includes reflections.

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.

This yields The formula may be further simplified if we sum up cycle indices over every

: There is a useful recursive formula for the cycle index of the symmetric group.

This yields the recurrence or 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 (see #Example for the case k = 2), for 1 ≤ k ≤ n. Let fk and Fk denote the number of orbits of G in these actions respectively.

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.

An overview of the most important results may be found at random permutation statistics.