Incombinatorialmathematics acycle index is apolynomial in several variables which is structured in such a way that information about how agroup of permutationsacts on aset can be simply read off from thecoefficients and exponents. This compact way of storing information in analgebraic form is frequently used incombinatorial enumeration.

Each permutation π of afinite set of objectspartitions that set intocycles; thecycle index monomial of π is amonomial in variablesa₁,a₂, … that describes thecycle type of this partition: the exponent ofa_i is the number of cycles of π of size i. Thecycle index polynomial of a permutation group is the average of the cycle index monomials of its elements. The phrasecycle indicator is also sometimes used in place ofcycle index.

Knowing the cycle index polynomial of a permutation group, one can enumerateequivalence classes due to thegroup'saction. This is the main ingredient in thePólya enumeration theorem. Performing formal algebraic anddifferential operations on these polynomials and then interpreting the results combinatorially lies at the core ofspecies theory.

Abijective map from a setX onto itself is called a permutation ofX, and the set of all permutations ofX forms a group under thecomposition of mappings, called thesymmetric group ofX, and denoted Sym(X ). Everysubgroup of Sym(X ) is called apermutation group ofdegree |X |.^[1] LetG be anabstract group with agroup homomorphism φ fromG into Sym(X ). Theimage, φ(G), is a permutation group. The group homomorphism can be thought of as a means for permitting the groupG to "act" on the setX (using the permutations associated with the elements ofG). Such a group homomorphism is formally called apermutation representation ofG. A given group can have many different permutation representations, corresponding to different actions.^[2]

Suppose that groupG acts on setX (that is, a group action exists). In combinatorial applications the interest is in the setX; for instance, counting things inX and knowing what structures might be left invariant byG. 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 thekernels 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 setX = {1,2, ...,n}. A permutation in this setting can be represented by a two-line notation. Thus,

corresponds to a bijection onX = {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 ofX 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 acyclic permutation because it "cycles" the numbers around, and a third notation for it would be (1 2 3 4 5). Thiscycle 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. Thelength 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 havefixed 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 ofX and form a partition ofX.

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₂ anda₃ (in general, use the variablea_k to correspond to lengthk cycles). The variablea_i will be raised to thej_i (g) power wherej_i (g) is the number of cycles of lengthi in the cycle decomposition of permutationg. We can then associate thecycle index monomial

${\displaystyle \prod _{k=1}^n{a}_k^{j_k(g)}}$

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

Thecycle index of apermutation groupG is the average of the cycle index monomials of all the permutationsg inG.

More formally, letG be a permutation group oforderm and degreen.Every permutationg inG has a unique decomposition into disjoint cycles, sayc₁c₂c₃ ... .Let the length of a cyclec be denoted by |c |.

Now letj_k(g) be the number of cycles ofg of lengthk, where

${\displaystyle 0\le j_k(g)\le \lfloor n/k\rfloor \text{ and }\sum _{k=1}^{n}k{j}_k(g)=n.}$

We associate tog the monomial

${\displaystyle \prod _{c\in g}{a}_{|c|}=\prod _{k=1}^n{a}_k^{j_k(g)}}$

in the variablesa₁,a₂, ...,a_n.

Then the cycle indexZ(G) ofG is given by

${\displaystyle Z(G)=\frac{1}{|G|}\sum _{g\in G}\prod _{k=1}^n{a}_k^{j_k(g)}.}$

Consider the groupG ofrotational symmetries of asquare in theEuclidean 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 ofG as permutations of the setX = {1,2,3,4}.^[8] The permutation representation ofG 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-clockwiserotations by 90°, 180°, 270° and 360° respectively. Notice that theidentity permutation e is the only permutation with fixed points in this representation ofG. As an abstract group,G is known as thecyclic groupC₄, and this permutation representation of it is itsregular representation. The cycle index monomials area₄,a₂²,a₄, anda₁⁴ respectively. Thus, the cycle index of this permutation group is:

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

The groupC₄ also acts on the unordered pairs of elements ofX in a natural way. Any permutationg would send {x,y} → {x^g,y^g} (wherex^g is the image of the elementx under the permutationg).^[9] The setX is now {A,B,C,D,E,F} whereA = {1,2},B = {2,3},C = {3,4},D = {1,4},E = {1,3} andF = {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 thecomplete graphK₄. Acting on this new set, the four group elements are now represented by (ADCB)(EF), (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:

${\displaystyle Z(C_4)=\frac{1}{4}\left(a_1^6+a_1^2{a}_2^2+2a_2{a}_4\right).}$

The groupC₄ can also act on the ordered pairs of elements ofX in the same natural way. Any permutationg would send (x,y) → (x^g,y^g) (in this case we would also have ordered pairs of the form (x,x)). The elements ofX could be thought of as the arcs of thecomplete digraphD₄ (withloops at each vertex). The cycle index in this case would be:

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

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 theidentity homomorphism. This is referred to as thenatural action.

The symmetric groupS₃ in its natural action has the elements^[10]

${\displaystyle S_3=\{e,(23),(12),(123),(132),(13)\}}$

and so, its cycle index is:

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

A permutation groupG on the setX istransitive if for every pair of elementsx andy inX there is at least oneg inG such thaty =x^g. A transitive permutation group isregular (or sometimes referred to assharply transitive) if the only permutation in the group that has fixed points is the identity permutation.

Afinite transitive permutation groupG on the setX is regularif 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 theregular representation of the group.

The cyclic groupC₆ in itsregular 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:

${\displaystyle Z(C_6)=\frac{1}{6}\left(a_1^6+a_2^3+2a_3^2+2a_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.

We will identify the complete graphK₃ with anequilateral triangle in the Euclidean plane. This permits us to use geometric language to describe the permutations involved assymmetries of the triangle. Every permutation in the groupS₃ ofvertex 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${\displaystyle a_1^3.}$
• Threereflections 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${\displaystyle 3a_1{a}_2.}$
• Two rotations, one clockwise, the other counterclockwise: These create a cycle of three edges; the contribution is${\displaystyle 2a_3.}$

The cycle index of the groupG of edge permutations induced by vertex permutations fromS₃ is

${\displaystyle Z(G)=\frac{1}{6}\left(a_1^3+3a_1{a}_2+2a_3\right).}$

It happens that the complete graphK₃ isisomorphic to its ownline graph (vertex-edge dual) and hence the edge permutation group induced by the vertex permutation group is the same as the vertex permutation group, namelyS₃ and the cycle index isZ(S₃). This is not the case for complete graphs on more than three vertices, since these have strictly more edges (${\displaystyle (\genfrac{}{}{0ex}{}{n}{2})}$) than vertices (${\displaystyle n}$).

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${\displaystyle 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${\displaystyle 6a_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${\displaystyle 8a_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${\displaystyle 3a_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${\displaystyle 6a_2{a}_4.}$

We may visualize the types of permutations geometrically assymmetries 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.
• Sixrotoreflections by 90 degrees.

The cycle index of the edge permutation groupG ofK₄ is:

${\displaystyle Z(G)=\frac{1}{24}\left(a_1^6+9a_1^2{a}_2^2+8a_3^2+6a_2{a}_4\right).}$

Consider an ordinarycube in three-space and its group of symmetries, call itC. It permutes the six faces of the cube.(We could also consider edge permutations or vertex permutations.)There are twenty-four symmetries.

• The identity:

There is one such permutation and its contribution is${\displaystyle 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 facesparallel to the axis of rotation. The contribution is${\displaystyle 6a_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${\displaystyle 3a_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 amain diagonal). This creates two three-cycles of faces (the faces incident on the same vertex form a cycle). The contribution is${\displaystyle 8a_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${\displaystyle 6a_2^3.}$

The conclusion is that the cycle index of the groupC is

${\displaystyle Z(C)=\frac{1}{24}\left(a_1^6+6a_1^2{a}_4+3a_1^2{a}_2^2+8a_3^2+6a_2^3\right).}$

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

${\displaystyle Z(E_n)=a_1^n.}$

Acyclic group,C_n is the group of rotations of aregularn-gon, that is,n elements equally spaced around a circle. This group has φ(d ) elements oforderd for eachdivisord ofn, where φ(d ) is theEuler φ-function, giving the number of natural numbers less thand which arerelatively prime tod. In the regular representation ofC_n, a permutation of orderd hasn/d cycles of lengthd, thus:^[12]

${\displaystyle Z(C_n)=\frac{1}{n}\sum _{d|n}\phi (d)a_d^{n/d}.}$

Thedihedral group is like thecyclic group, but also includes reflections. In its natural action,

The cycle index of thealternating group in its natural action as a permutation group is

${\displaystyle Z(A_n)=\sum _{j_1+2j_2+3j_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 theeven permutations, and 0 for theodd permutations. The 2 is needed because${\displaystyle \frac{1}{|A_n|}=\frac{2}{n!}}$.

The cycle index of thesymmetric groupS_n in its natural action is given by the formula:

${\displaystyle Z(S_n)=\sum _{j_1+2j_2+3j_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 completeBell polynomials:

${\displaystyle 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 ofn labels into subsets, where there are${\displaystyle j_k}$ subsets of sizek. Every such subset generates${\displaystyle k!/k}$ cycles of lengthk. But we do not distinguish between cycles of the same size, i.e. they are permuted by${\displaystyle S_{j_k}}$. This yields

${\displaystyle \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!}.}$

The formula may be further simplified if we sum up cycle indices over every${\displaystyle n}$, while using an extra variable${\displaystyle y}$ to keep track of the total size of the cycles:

${\displaystyle \sum _{n\ge 1}{y}^{n}Z(S_n)=\sum _{n\ge 1}\sum _{j_1+2j_2+3j_3+\cdots +n{j}_n=n}\prod _{k=1}^n\frac{a_k^{j_k}{y}^{k{j}_k}}{k^{j_k}{j}_k!}=\prod _{k\ge 1}\sum _{j_k\ge 0}\frac{(a_k{y}^k{)}^{j_k}}{k^{j_k}{j}_k!}=\prod _{k\ge 1}\exp \left(\frac{a_k{y}^k}{k}\right),}$

thus giving a simplified form for the cycle index of${\displaystyle S_n}$:

There is a useful recursive formula for the cycle index of the symmetric group.Set${\displaystyle Z(S_0)=1}$ and consider the sizel of the cycle that containsn,where${\displaystyle \begin{array}{c}1\le l\le n.\end{array}}$There are$(\genfrac{}{}{0ex}{}{n-1}{l-1})$ ways to choose the remaining${\displaystyle l-1}$ elements of the cycle and every such choice generates${\displaystyle \begin{array}{c}\frac{l!}{l}=(l-1)!\end{array}}$ different cycles.

This yields the recurrence

${\displaystyle 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(\genfrac{}{}{0ex}{}{n-1}{l-1})(l-1)!a_l(n-l)!Z(S_{n-l})}$

or

${\displaystyle Z(S_n)=\frac{1}{n}\sum _{l=1}^n{a}_{l}Z(S_{n-l}).}$

Throughout this section we will modify the notation for cycle indices slightly by explicitly including the names of the variables. Thus, for the permutation groupG we will now write:

${\displaystyle Z(G)=Z(G;a_1,a_2,\dots ,a_n).}$

LetG be a group acting on the setX.G also induces an action on thek-subsets ofX and on thek-tuples of distinct elements ofX (see#Example for the casek = 2), for 1 ≤k ≤n. Letf_k andF_k denote the number oforbits ofG in these actions respectively. By convention we setf₀ =F₀ = 1. We have:^[13]

a) Theordinary generating function forf_k is given by:

${\displaystyle \sum _{k=0}^n{f}_k{t}^k=Z(G;1+t,1+t^2,\dots ,1+t^n),}$ and

b) Theexponential generating function forF_k is given by:

${\displaystyle \sum _{k=0}^n{F}_k{t}^k/k!=Z(G;1+t,1,1,\dots ,1).}$

LetG be a group acting on the setX andh a function fromX toY. For anyg inG,h(x^g) is also a function fromX toY. Thus,G induces an action on the setY^X of all functions fromX toY. The number of orbits of this action is Z(G;b,b, ...,b) whereb = |Y |.^[14]

This result follows from theorbit counting lemma (also known as the Not Burnside's lemma, but traditionally called Burnside's lemma) and the weighted version of the result isPó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 andintegrated. The area ofsymbolic 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 theanalysis of algorithms. An overview of the most important results may be found atrandom permutation statistics.

• 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

• Marko Riedel,Pólya's enumeration theorem and the symbolic method
• Marko Riedel,Cycle indices of the set / multiset operator and the exponential formula
• 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.
• Harald Fripertinger (1992)."Enumeration in Musical Theory".Beiträge zur Elektronischen Musik.1.

• Combinatorics
• Enumerative combinatorics

• Articles with short description
• Short description matches Wikidata