Cycle Index - Applications

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 (see #Example for the case k = 2), for 1 ≤ k ≤ n. Let f_k and F_k denote the number of orbits of G in these actions respectively. By convention we set f₀ = F₀ = 1. We have:

a) The ordinary generating function for f_k is given by:

and

b) The exponential generating function for F_k 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(xg) 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(G; b, b, ...,b) where b = |Y|.

This result follows from the orbit counting lemma (also known as the Not Burnside's lemma, but traditionally called Burnside's 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.