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

Let X be a set. A bijective map from X onto itself is called a permutation and the set of all permutations of X forms a group under the composition of mappings, called the Symmetric group of X, Sym(X). Every subgroup of Sym(X) is called a permutation group of degree |X|.^[1] Let G be an abstract group with a group homomorphism,φ, from G into Sym(X). The image, φ(G), 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 (using the permutations associated with the elements of G). 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.^[2]

Suppose that group G acts on set X (that is, a group action exists). 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.^[3]

Disjoint cycle representation of permutations

Finite permutations are most often represented as group actions on the set X = {1,2, ..., n}. A permutation in this setting can be represented by a two line notation. Thus,

\left ( \begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{matrix} \right )

corresponds to a bijection on X = {1, 2, 3, 4, 5} 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 [2 3 4 5 1].^[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). 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 (it "cycles" to the beginning). With cycle notation, it does not matter where a cycle starts, so (1 2 3 4 5) and (3 4 5 1 2) and (5 1 2 3 4) 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^[5] of disjoint (having no common element) cycles in essentially one way.^[6] As a permutation may have fixed points (elements that are unchanged by the permutation), these will be represented by cycles of length one. For example:^[7]

\left ( \begin{matrix}1 & 2 & 3 & 4& 5& 6\\2&1&3&5&6&4 \end{matrix} \right ) = (1 2)(3)(4 5 6).

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 (dummy) 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, a₁, a₂ and a₃ (in general, use the variable a_k to correspond to length k cycles). The variable a_i will be raised to the j_i(g) power where j_i(g) is the number of cycles of length i in the cycle decomposition of permutation g. We can then associate the cycle index monomial

\prod_{k=1}^n a_k^{j_k(g)}

to the permutation g. The cycle index monomial of our example would be a₁a₂a₃, while the cycle index monomial of the permutation (1 2)(3 4)(5)(6 7 8 9)(10 11 12 13)(14)(15) would be a₁³a₂²a₄².

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

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 (consecutively going clockwise) we can represent the elements of G as permutations of the set X = {1,2,3,4}.^[8] The permutation representation of G consists of the four permutations (1 4 3 2), (1 3)(2 4), (1 2 3 4) and e = (1)(2)(3)(4) 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 C₄, and this permutation representation of it is its regular representation. The cycle index monomials are a₄, a₂², a₄, and a₁⁴ respectively. Thus, the cycle index of this permutation group is:

Z(C_4) = \frac{1}{4}\left ( a_1^4 + a_2^2 + 2a_4 \right).

The group C₄ also acts on the unordered pairs of elements of X in a natural way. Any permutation g would send {x,y} → {x^g, y^g} (where x^g is the image of the element x under the permutation g).^[9] The set X is now {A, B, C, D, E, F} where A = {1,2}, B = {2,3}, C = {3,4}, D = {1,4}, E = {1,3} and F = {2,4}. 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 K₄. 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:

Z(C_4) = \frac{1}{4}\left ( a_1^6 + a_1^2 a_2^2 + 2a_2a_4 \right).

The group C₄ 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 D₄ (with loops at each vertex). The cycle index in this case would be:

Z(C_4) = \frac{1}{4}\left ( a_1^{16} + a_2^8 + 2a_4^4 \right).

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 S₃ in its natural action has the elements^[10]

S_3 = \{e,(2 3),(1 2),(1 2 3),(1 3 2),(1 3)\}

and so, its cycle index is:

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

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 = x^g. A transitive permutation group is regular (or sometimes referred to as sharply transitive) 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|.^[11] Cayley's theorem states that every abstract group has a regular permutation representation given by the group acting on itself (as a set) by (right) multiplication. This is called the regular representation of the group.

The cyclic group C₆ in its regular representation contains the six permutations (one-line form of the permutation is given first):

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

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

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 K₃ 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 S₃ of vertex permutations (S₃ in its natural action, given above) induces an edge permutation. 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 the complete graph K₃ is isomorphic to its own line graph (vertex-edge 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 complete graphs on more than three vertices, since these have strictly more edges ( $\binom{n}{2}$ ) than vertices (n).

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 (S₄ in its natural action) and the edge permutations (S₄ acting on unordered pairs) 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 cycle the vertices in 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.\,$

We may visualize the types of permutations geometrically 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.

The cycle index of the edge permutation group G of K₄ 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).

The cycle index of the face permutations of a cube

Cube with colored faces

Consider an ordinary cube in three-space and its group of symmetries (automorphisms), 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.

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 permutation groups

Identity group E_n

This group contains one permutation that fixes every element (this must be a natural action).

Z(E_n) = a_1^n.

Cyclic group C_n

A Cyclic group, C_n is the group of rotations of a regular n-gon, that is, n elements equally spaced around a circle. 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 C_n, a permutation of order d has n/d cycles of length d, thus:^[12]

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

Dihedral group D_n

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

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 cycle index of the alternating group in its natural action as a permutation group is

Z(A_n) = \sum_{j_1+2 j_2 + 3 j_3 + \cdots + n j_n = 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 numerator is 2 for the even permutations, and 0 for the odd permutations. The 2 is needed because $\frac{1}{|A_n|}=\frac{2}{n!}$ .

The symmetric group S_n

The cycle index of the symmetric group S_n in its natural action is given by the formula:

Z(S_n) = \sum_{j_1+2 j_2 + 3 j_3 + \cdots + n j_n = 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_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}).

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:

Z(G) = Z(G; a_1, a_2, \ldots, a_n).

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:^[13]

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

\sum_{k=0}^n f_k t^k = Z(G; 1+t, 1+t^2, \ldots, 1+t^n),

and

b) The exponential generating function for F_k is given by:

\sum_{k=0}^n F_k t^k/k! = Z(G; 1+t, 1, 1, \ldots, 1).

Let G be a group acting on the set X and h a function from X to Y. For any g in G, h(x^g) is also a function from X to Y. Thus, G induces an action on the set Y^X of all functions from X to Y. The number of orbits of this action is Z(G; b, b, ...,b) where b = |Y|.^[14]

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.

Notes

↑ Dixon & Mortimer 1996, pg. 2, section 1.2 Symmetric groups
↑ Cameron 1994, pp. 227–228
↑ Cameron 1994, pg. 231, section 14.3
↑ This notational style is frequently found in the computer science literature.
↑ Cyclic permutations are functions and the term product really means composition of these functions.
↑ Up to the different ways one can write a cycle and the fact that disjoint cycles commute so they can be written in any order.
↑ Roberts & Tesman 2009, pg. 473
↑ Technically we are using the notion of equivalence of group actions, replacing G acting on the corners of the square by the permutation representation of G acting on X. For the purposes of exposition, it is better to slide over these details.
↑ This notation is common amongst geometers and combinatorialists. It is used instead of the more common g(x) for traditional reasons.
↑ There is a convention to not write the fixed points in the cycle notation for a permutation, but these must be represented in the cycle index.
↑ Dixon & Mortimer 1996, pg. 9, Corollary 1.4A(iii)
↑ van Lint & Wilson 1992, pg. 464, Example 35.1
↑ Cameron 1994, pg. 248, Proposition 15.3.1
↑ van Lint & Wilson 1992, pg. 463, Theorem 35.1

References

Brualdi, Richard A. (2010), "14. Pólya Counting", Introductory Combinatorics (5th ed.), Upper Saddle River, NJ: Prentice Hall, pp. 541–575, ISBN 978-0-13-602040-0

Cameron, Peter J. (1994), "15. Enumeration under group action", Combinatorics:Topics, Techniques, Algorithms, Cambridge: Cambridge University Press, pp. 245–256, ISBN 0-521-45761-0

Dixon, John D.; Mortimer, Brian (1996), Permutation Groups, New York: Springer, ISBN 0-387-94599-7

Roberts, Fred S.; Tesman, Barry (2009), "8.5 The Cycle Index", Applied Combinatorics (2nd ed.), Boca Raton: CRC Press, pp. 472–479, ISBN 978-1-4200-9982-9

Tucker, Alan (1995), "9.3 The Cycle Index", Applied Combinatorics (3rd ed.), New York: Wiley, pp. 365–371, ISBN 0-471-59504-7

van Lint, J.H.; Wilson, R.M. (1992), "35.Pólya theory of counting", A Course in Combinatorics, Cambridge: Cambridge University Press, pp. 461–474, ISBN 0-521-42260-4

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.

This article is issued from Wikipedia - version of the Monday, March 23, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.