View source for Mason–Weaver equation

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 [[Partition of a set|partitions]] that set into [[cycle (mathematics)|cycle]]s; the '''cycle index monomial''' of π is a [[monomial]] in variables ''a''<sub>1</sub>, ''a''<sub>2</sub>, … that describes the type of this partition (the '''cycle type''' of π): the exponent of ''a''<sub>''i''</sub> is the number of cycles of π of size&nbsp;''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 [[Polya theorem|Pólya's enumeration theorem]]. Performing formal algebraic and differential operations on these polynomials and then interpreting the results combinatorially lies at the core of [[combinatorial species|species theory]].

==Permutation groups and group actions==

Let ''X'' be a set. A [[Bijective mapping|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'',<br /> '''Sym'''(''X''). Every [[subgroup]] of Sym(''X'') is called a [[permutation group]] of ''degree'' |''X''|.<ref>{{harvnb|Dixon|Mortimer|1996|loc=pg. 2, section 1.2 Symmetric groups}}</ref> 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.<ref>{{harvnb|Cameron|1994|loc=pp. 227-228}}</ref>

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 [[Kernel (algebra)|kernels]] of the group actions, which measure how much is lost in passing from the group to its permutation representation.<ref>{{harvnb|Cameron|1994|loc=pg. 231, section 14.3}}</ref>

== 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,
:: <math>\left ( \begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{matrix} \right )</math>
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].<ref>This notational style is frequently found in the computer science literature.</ref> 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<ref>Cyclic permutations are functions and the term ''product'' really means ''composition'' of these functions.</ref> of disjoint (having no common element) cycles in essentially one way.<ref>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.</ref> 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:<ref>{{harvnb|Roberts|Tesman|2009|loc=pg. 473}}</ref>
:: <math>\left ( \begin{matrix}1 & 2 & 3 & 4& 5& 6\\2&1&3&5&6&4 \end{matrix} \right ) = (1 2)(3)(4 5 6).</math>
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 a set|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''<sub>1</sub>, ''a''<sub>2</sub> and ''a''<sub>3</sub> (in general, use the variable ''a''<sub>''k''</sub> to correspond to length ''k'' cycles). The variable ''a''<sub>''i''</sub> will be raised to the ''j''<sub>''i''</sub>(''g'') power where ''j''<sub>''i''</sub>(''g'') is the number of cycles of length ''i'' in the cycle decomposition of permutation ''g''. We can then associate the ''cycle index monomial''
:: <math>\prod_{k=1}^n a_k^{j_k(g)}</math>
to the permutation ''g''. The cycle index monomial of our example would be ''a''<sub>1</sub>''a''<sub>2</sub>''a''<sub>3</sub>, 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''<sub>1</sub><sup>3</sup>''a''<sub>2</sub><sup>2</sup>''a''<sub>4</sub><sup>2</sup>.

==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''<sub>1</sub> ''c''<sub>2</sub> ''c''<sub>3</sub> ... .
Let the length of a cycle ''c'' be denoted by |''c''|.

Now let ''j''<sub>k</sub>(g) be the number of cycles of ''g'' of length ''k'', where

:<math>0 \le j_k(g) \le \lfloor n/k \rfloor \mbox{ and }
\sum_{k=1}^n k \, j_k(g) \; = n.</math>

We associate to ''g'' the monomial
:<math> \prod_{c\in g} a_{|c|} = \prod_{k=1}^n a_k^{j_k(g)}</math>
in the variables ''a''<sub>1</sub>, ''a''<sub>2</sub>, ... , ''a''<sub>''n''</sub>.

Then the cycle index ''Z''(''G'') of ''G'' is given by

:<math> Z(G) = \frac{1}{|G|} \sum_{g\in G} \prod_{k=1}^n a_k^{j_k(g)}.</math>

== Example ==

Consider the group ''G'' of [[rotational symmetries]] of a [[Square (geometry)|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}.<ref>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.</ref> 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''<sub>4</sub>, and this permutation representation of it is its ''regular representation''.  The cycle index monomials are ''a''<sub>4</sub>, ''a''<sub>2</sub><sup>2</sup>, ''a''<sub>4</sub>, and ''a''<sub>1</sub><sup>4</sup> respectively. Thus, the cycle index of this permutation group is:
:: <math>Z(C_4) = \frac{1}{4}\left ( a_1^4 + a_2^2 + 2a_4 \right).</math>

The group ''C''<sub>4</sub> also acts on the unordered pairs of elements of ''X'' in a natural way. Any permutation ''g'' would send {''x'',''y''} → {''x''<sup>''g''</sup>, ''y''<sup>''g''</sup>} (where ''x''<sup>''g''</sup> is the image of the element ''x'' under the permutation ''g'').<ref>This notation is common amongst geometers and combinatorialists. It is used instead of the more common g(x) for traditional reasons.</ref> 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''<sub>4</sub>. 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:
:: <math>Z(C_4) = \frac{1}{4}\left ( a_1^6 + a_1^2 a_2^2 + 2a_2a_4 \right).</math>

The group ''C''<sub>4</sub> can also act on the ordered pairs of elements of ''X'' in the same natural way. Any permutation ''g'' would send (''x'',''y'') → (''x''<sup>''g''</sup>, ''y''<sup>''g''</sup>) (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''<sub>4</sub> (with loops at each vertex). The cycle index in this case would be: 
:: <math>Z(C_4) = \frac{1}{4}\left ( a_1^{16} + a_2^8 + 2a_4^4 \right).</math>

==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''<sub>3</sub> in its natural action has the elements<ref>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.</ref>
:<math>S_3 = \{e,(2 3),(1 2),(1 2 3),(1 3 2),(1 3)\}</math>
and so, its cycle index is:
:: <math>Z(S_3) = \frac{1}{6} 
\left( a_1^3 + 3 a_1 a_2 + 2 a_3 \right).</math>

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''<sup>''g''</sup>. 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''|.<ref>{{harvnb|Dixon|Mortimer|1996|loc=pg. 9, Corollary 1.4A(iii)}}</ref> [[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''<sub>6</sub> 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:
:<math>Z(C_6) = \frac{1}{6} 
\left( a_1^6 + a_2^3 + 2 a_3^2 + 2 a_6 \right).</math>

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''<sub>3</sub> 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''<sub>3</sub> of ''vertex permutations'' (''S''<sub>3</sub> 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 <math>a_1^3.\,</math>
* 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 <math>3 a_1 a_2.\,</math>
* Two rotations, one clockwise, the other counterclockwise: These create a cycle of three edges; the contribution is <math>2 a_3.\,</math>

The cycle index of the group ''G'' of edge permutations induced by vertex permutations 
from ''S''<sub>3</sub> is
:<math> Z(G) = \frac{1}{6} \left(a_1^3 + 3 a_1 a_2 + 2 a_3 \right).</math>

It happens that the complete graph ''K''<sub>3</sub> 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''<sub>3</sub> and the cycle index is ''Z''(''S''<sub>3</sub>). This is not the case for complete graphs on more than three vertices, since these have strictly more edges (<math>\binom{n}{2}</math>) 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''<sub>4</sub> in its natural action) and the edge permutations (''S''<sub>4</sub> acting on unordered pairs) that they induce:

* The identity: This permutation maps all vertices (and hence, edges) to themselves and the contribution is <math>a_1^6.\,</math>
* 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 <math>6 a_1^2 a_2^2.\,</math>
* 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 <math>8 a_3^2.\,</math>
* 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 <math>3 a_1^2 a_2^2.\,</math>
* 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 <math>6 a_2 a_4.\,</math>

We may visualize the types of permutations geometrically as [[Tetrahedral symmetry|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 permuation group ''G'' of ''K''<sub>4</sub> is:
:<math>
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).
</math>

===The cycle index of the face permutations of a cube===

[[Image:Face colored cube.png|thumb|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 <math>a_1^6.</math>
* 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 <math>6 a_1^2 a_4.</math>
* 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 <math>3 a_1^2 a_2^2.</math>
* 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 <math>8 a_3^2.</math>
* 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 <math>6 a_2^3.</math>

The conclusion is that the cycle index of the group ''C'' is
:<math>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)
.</math>

==Cycle indices of some permutation groups==

===Identity group ''E''<sub>''n''</sub>===
This group contains one permutation that fixes every element (this must be a natural action).

:<math> Z(E_n) = a_1^n.</math>

===Cyclic group ''C''<sub>n</sub>===
A [[Cyclic group]], ''C''<sub>n</sub> 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's totient function|Euler φ-function]], giving the number of natural numbers less than ''d'' which are relatively prime to ''d''. In the regular representation of ''C''<sub>n</sub>, a permutation of order ''d'' has ''n''/''d'' cycles of length ''d'', thus:<ref>{{harvnb|van Lint|Wilson|1992|loc=pg. 464, Example 35.1}}</ref>

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

===Dihedral group ''D''<sub>n</sub>===
[[Dihedral group]] is like the [[cyclic group]], but also includes reflections. In its natural action,

:<math> 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}
</math>

===The alternating group ''A''<sub>n</sub>===
The cycle index of the [[alternating group]] in its natural action as a permutation group is

:<math> 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}.
</math>
The numerator is 2 for the even permutations, and 0 for the odd permutations. The 2 is needed because
<math>\frac{1}{|A_n|}=\frac{2}{n!}</math>.

===The symmetric group ''S''<sub>n</sub>===

The cycle index of the [[symmetric group]] ''S''<sub>n</sub> in its natural action is given by the formula:
:<math> 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}</math>
that can be also stated in terms of complete [[Bell polynomial]]s:
:<math> Z(S_n) = \frac{B_n(0!\,a_1, 1!\,a_2, \dots, (n-1)!\,a_n)}{n!}.</math>

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 <math>j_k</math> subsets of size ''k''. Every such subset generates <math>k!/k</math> cycles of length ''k''. But we do not distinguish between cycles of the same size, i.e. they are permuted by <math>S_{j_k}</math>. This yields
:<math>
\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!}.</math>

There is a useful recursive formula for the cycle index of the symmetric group.
Set <math>Z(S_0) = 1</math> and consider the size ''l'' of the cycle that contains ''n'',
where <math>\begin{matrix}1 \le l \le n.\end{matrix}</math> 
There are <math>\begin{matrix}{n-1 \choose l-1}\end{matrix}</math> ways to choose
the remaining <math>l-1</math> elements of the cycle and every such choice generates
<math>\begin{matrix}\frac{l!}{l}\end{matrix}</math> different cycles.  

This yields the recurrence
:<math> 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})
</math>
or
:<math>
Z(S_n) =  \frac{1}{n} \sum_{l=1}^n a_l \; Z(S_{n-l}).</math>

== 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:
:: <math>Z(G) = Z(G; a_1, a_2, \ldots, a_n).</math>

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''<sub>''k''</sub> and ''F''<sub>''k''</sub> denote the number of [[orbit (group theory)|orbits]] of ''G'' in these actions respectively. By convention we set ''f''<sub>0</sub> = ''F''<sub>0</sub> = 1. We have:<ref>{{harvnb|Cameron|1994|loc= pg. 248, Proposition 15.3.1}}</ref>

a) The [[ordinary generating function]] for ''f''<sub>''k''</sub> is given by:
:: <math>\sum_{k=0}^n f_k t^k = Z(G; 1+t, 1+t^2, \ldots, 1+t^n),</math> and
b) The [[exponential generating function]] for ''F''<sub>''k''</sub> is given by:
:: <math>\sum_{k=0}^n F_k t^k/k! = Z(G; 1+t, 1, 1, \ldots, 1).</math>

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''<sup>''g''</sup>) is also a function from ''X'' to ''Y''. Thus, ''G'' induces an action on the set ''Y''<sup>''X''</sup> of all functions from ''X'' to ''Y''. The number of orbits of this action is Z(''G''; ''b'', ''b'', ...,''b'') where ''b'' = |''Y''|.<ref>{{harvnb|van Lint|Wilson|1992|loc= pg. 463, Theorem 35.1}}</ref>

This result follows from the [[Burnside's lemma|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 ==
{{reflist}}

== References ==

* {{citation|last=Brualdi|first=Richard A.|title=Introductory Combinatorics|edition=5th|publisher=Prentice Hall|place=Upper Saddle River, NJ|year=2010|chapter=14. Pólya Counting|isbn=978-0-13-602040-0|pages=541–575}}

* {{citation|last=Cameron|first=Peter J.|title=Combinatorics:Topics, Techniques, Algorithms|publisher=Cambridge University Press|place=Cambridge|year=1994|chapter=15. Enumeration under group action|pages=245–256|isbn=0-521-45761-0}}

* {{citation|last1=Dixon|first1=John D.|last2=Mortimer|first2=Brian|title=Permutation Groups|publisher=Springer|place=New York|year=1996|isbn=0-387-94599-7}}

* {{citation|last1=Roberts|first1=Fred S.|last2=Tesman|first2=Barry|title=Applied Combinatorics|edition=2nd|publisher=CRC Press|year=2009|place=Boca Raton|isbn=978-1-4200-9982-9|chapter=8.5 The Cycle Index|pages=472–479}}

* {{citation|last=Tucker|first=Alan|title=Applied Combinatorics|edition=3rd|publisher=Wiley|place=New York|year=1995|chapter=9.3 The Cycle Index|pages=365–371|isbn=0-471-59504-7}}

* {{citation|last1=van Lint|first1=J.H.|last2=Wilson|first2=R.M.|title=A Course in Combinatorics|publisher=Cambridge University Press|place=Cambridge|year=1992|chapter=35.Pólya theory of counting|pages=461–474|isbn=0-521-42260-4}}

== External links ==

* Marko Riedel, ''[http://www.mathematik.uni-stuttgart.de/~riedelmo/papers/collier.pdf Pólya's enumeration theorem and the symbolic method]''

* {{cite journal |author=Harald Fripertinger |title=Cycle indices of linear, affine and projective groups |journal=Linear Algebra and Its Applications |year=1997 |volume=263 |pages=133–156 |url=http://www.uni-graz.at/~fripert/linaffproj.html |doi=10.1016/S0024-3795(96)00530-7}}

[[Category:Combinatorics]]
[[Category:Enumerative combinatorics]]