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 cycle 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.
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 |.[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 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]
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,
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]
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, a1, a2 and a3 (in general, use the variable ak to correspond to length k cycles). The variable ai will be raised to the ji (g) power where ji (g) 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 (1 2)(3 4)(5)(6 7 8 9)(10 11 12 13) would be a1a22a42.
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(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}.[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 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 {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 K4. 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). The cycle index in this case would be:
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[10]
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 = 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 C6 in its regular representation contains the six permutations (one-line form of the permutation is given first):
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.
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. Every permutation in the group S3 of vertex permutations (S3 in its natural action, given above) 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 (vertex-edge dual) 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(S3). This is not the case for complete graphs on more than three vertices, since these have strictly more edges ( ) than vertices ( ).
This is entirely analogous to the three-vertex case. These are the vertex permutations (S4 in its natural action) and the edge permutations (S4 acting on unordered pairs) 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:
Consider an ordinary cube in three-space and its group of symmetries, call it C. It permutes the six faces of the cube. (We could also consider edge permutations or vertex permutations.) There are twenty-four symmetries.
The conclusion is that the cycle index of the group C is
This group contains one permutation that fixes every element (this must be a natural action).
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 φ(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. In its natural action,
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 .
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
The formula may be further simplified if we sum up cycle indices over every , while using an extra variable to keep track of the total size of the cycles:
thus giving a simplified form for the cycle index of :
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
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. By convention we set f0 = F0 = 1. We have:[13]
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(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.