# Cycle index
The cycle index of a permutation group is a polynomial that records, for each way of decomposing a permutation into disjoint cycles, how many group elements have that cycle structure, averaged over the whole group. It is the central object of Pólya's theory of combinatorial enumeration: evaluating the polynomial at a single point counts the distinct colorings, graphs, or chemical structures that remain after identifying configurations related by symmetry.
| Key fact | Detail |
|---|---|
| Definition | For a permutation group \( G \) on a set \( X \), \( Z_G = \frac{1}{\|G\|} \sum_{g \in G} x_1^{j_1(g)} x_2^{j_2(g)} \cdots \), where \( j_k(g) \) is the number of cycles of length \( k \) in \( g \)[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html) |
| Origin | Introduced by G. Pólya in "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen", *Acta Mathematica* 68, pp. 145–254 (1937)[2](https://portal.mardi4nfdi.de/wiki/Publication%3A2645775) |
| Anticipation | J. Howard Redfield published the underlying idea in 1927 in the *American Journal of Mathematics* (Vol. 49, No. 3, pp. 433–455), but it was overlooked[3](https://www.jstor.org/stable/2370675) |
| Main use | By Pólya's theorem, the number of orbits of \( G \) acting on all functions from \( X \) to a \( k \)-element set is \( Z_G(k, \ldots, k) \)[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html) |
| Worked count | 6-bead necklaces with 3 colors: \( \frac{1}{12}(3^6 + 3 \cdot 3^2 3^2 + 4 \cdot 3^3 + 2 \cdot 3^2 + 2 \cdot 3) = 92 \)[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html) |
| Complexity | Computing a single coefficient of the cycle index from a set of generators is #P-hard for every fixed \( i > 1 \)[4](https://www.sciencedirect.com/science/article/pii/S089054018371045X) |
| Representation dependence | The cycle index depends on the specific permutation representation; isomorphic groups can give different cycle indices[5](https://cayley.academic.csusb.edu/content/papers/dcj.pdf) |
## Definition
Every element of a permutation group on a finite set decomposes into disjoint cycles. For a permutation \( g \), let \( j_k(g) \) denote the number of cycles of length \( k \). The cycle index polynomial is
\[ Z_G(x_1, \ldots, x_n) = \frac{1}{\|G\|} \sum_{g \in G} x_1^{j_1(g)} x_2^{j_2(g)} \cdots x_n^{j_n(g)}, \]
a polynomial with rational coefficients in one variable per possible cycle length[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html). The coefficient structure is a census of cycle types: multiplying by \( \|G\| \) turns each monomial's coefficient into the number of group elements with that cycle type. In the symmetric group \( S_4 \), for example, there is the identity, 6 transpositions, 3 products of two transpositions, 8 three-cycles, and 6 four-cycles, giving \( 24 \, Z_{S_4} = p_{[1,1,1,1]} + 6p_{[2,1,1]} + 3p_{[2,2]} + 8p_{[3,1]} + 6p_{[4]} \) in the power-sum notation used by computer algebra systems[6](https://doc.sagemath.org/html/en/reference/categories/sage/categories/finite_permutation_groups.html).
A permutation is written compactly by its cycle type: the reflection \( s = (16)(25)(34) \) of six beads consists of three 2-cycles and is represented by the monomial \( x_2^3 \)[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html).
## Role in Pólya enumeration
The polynomial earns its place through Pólya's theorem. Let \( G \) act on a set \( X \), let \( C \) be a set of size \( k \) (the colors), and let \( \Omega \) be the set of all functions from \( X \) to \( C \), with \( G \) acting naturally by permuting positions. Then the number of orbits of \( G \) on \( \Omega \), that is, the number of colorings distinct up to symmetry, is the evaluation \( Z_G(k, \ldots, k) \)[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html). The result follows from [Burnside's lemma](https://www.edgepedia.org/burnsides-lemma), which averages the number of fixed colorings over the group; a permutation fixes a coloring exactly when every cycle of the permutation lies within a single color, so a permutation with cycle type \( x_1^{j_1} x_2^{j_2} \cdots \) fixes \( k^{j_1 + j_2 + \cdots} \) colorings[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html).
**The necklace example.** For six beads under rotations and reflections, the dihedral group of order 12 has cycle index
\[ Z_G = \frac{1}{12} \left( x_1^6 + 3 x_1^2 x_2^2 + 4 x_2^3 + 2 x_3^2 + 2 x_6 \right), \]
combining the identity, five nontrivial rotations, and six reflections[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html). Substituting 3 for each variable gives \( (3^6 + 3 \cdot 3^2 3^2 + 4 \cdot 3^3 + 2 \cdot 3^2 + 2 \cdot 3)/12 = 92 \) distinct necklaces[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html). The same method with a 10-bead necklace and 3 colors gives \( P(3, \ldots, 3) = 3210 \)[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html).
The weighted form of the theorem is more flexible. Assigning each color a weight in a commutative ring and substituting the figure counting series \( \phi(x), \phi(x^2), \ldots \) into the cycle index yields a configuration counting series whose coefficients enumerate orbits by weight, for example by number of edges or by chemical composition[7](https://encyclopediaofmath.org/wiki/P%C3%B3lya_theorem).
## Known cycle indices
Closed forms exist for the standard families of groups. The cyclic group of order \( n \) has cycle index
\[ \frac{1}{n} \sum_{d \mid n} \phi(d) \, x_d^{n/d}, \]
where \( \phi \) is [Euler's totient function](https://www.edgepedia.org/eulers-totient-function)[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html). The symmetry group of a regular \( n \)-gon (the dihedral case) adds reflection terms: for odd \( n \) a term \( n x_1 x_2^{(n-1)/2} \), and for even \( n \) the two terms \( \frac{n}{2} x_1^2 x_2^{(n-2)/2} \) and \( \frac{n}{2} x_2^{n/2} \), all divided by \( 2n \)[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html). For the full symmetric group on \( n \) objects, the cycle index sums over all integer partitions \( \lambda_1 + 2\lambda_2 + \cdots + n\lambda_n = n \), with each monomial \( x_1^{\lambda_1} \cdots x_n^{\lambda_n} \) weighted by \( 1/(1^{\lambda_1} \lambda_1! \, 2^{\lambda_2} \lambda_2! \cdots n^{\lambda_n} \lambda_n!) \)[1](https://crypto.stanford.edu/~blynn/polya/cycleindex.html).
Cycle indices also compose. Pólya showed that the cycle index of the [Cartesian product](https://www.edgepedia.org/cartesian-product) \( A \times B \) acting on \( X \times Y \) is computed by averaging terms in which an \( i \)-cycle of \( A \) and a \( k \)-cycle of \( B \) contribute \( \gcd(i,k) \) cycles of length \( \operatorname{lcm}(i,k) \), while ordinary multiplication \( Z_A(s) Z_B(s) \) gives the cycle index for the disjoint union action, and that the cycle index of the wreath product \( A[B] \) is \( Z_A(t_1, t_2, t_3, \ldots) \) with \( t_k = Z_B(s_k, s_{2k}, s_{3k}, \ldots) \)[5](https://cayley.academic.csusb.edu/content/papers/dcj.pdf) • [14](https://www.mathe2.uni-bayreuth.de/frib/html/book/hyl00_60.html). Harary introduced a combinatorial multiplication of polynomials, often written \( \circledast \), that computes the cycle index of a product group from the cycle indices of its factors[8](https://doi.org/10.1515/jmc-2016-0042).
## Applications
Pólya's 1937 paper applied the method to the enumeration of chemical compounds, counting structural isomers of molecules under the symmetry group of the molecular skeleton[2](https://portal.mardi4nfdi.de/wiki/Publication%3A2645775). Graph enumeration followed: the group acting on the 2-subsets of a 4-element vertex set is \( S_4 \), whose cycle index on the six possible edges is \( \frac{1}{24}(t_1^6 + 9 t_1^2 t_2^2 + 8 t_3^2 + 6 t_2 t_4) \), and evaluating it counts the unlabeled graphs on four vertices[9](https://math.mit.edu/research/highschool/primes/materials/2018/conf/17-3%20Fan-ZhuS.pdf). Harary, Palmer, Robinson, and others used the wreath product formula to enumerate classes of graphs[5](https://cayley.academic.csusb.edu/content/papers/dcj.pdf). In coding theory, a cycle-index-like average over the permutation group constructed from a code underlies proofs of the MacWilliams identity[10](https://www.koji-imamura.org/en/resources/notes/macwilliams-08).
## Computation
The cycle index is a symmetric function, naturally expressed in the power-sum basis, and software such as Sage computes it for named permutation groups, including cyclic, dihedral, symmetric, and alternating groups, and derives cycle indices of induced actions on \( k \)-tuples and \( k \)-subsets[6](https://doc.sagemath.org/html/en/reference/categories/sage/categories/finite_permutation_groups.html) • [11](https://www.mathe2.uni-bayreuth.de/frib/html/symman/manual_20.html).
Exact computation from generators is hard. A 1993 study of the evaluation problem showed that determining the coefficient of \( x_i^{n/i} \) in the cycle index of a permutation group given by generators is #P-hard for every fixed \( i > 1 \), and there are complexity-theoretic reasons for believing no efficient uniform procedure computes the polynomial exactly[4](https://www.sciencedirect.com/science/article/pii/S089054018371045X) • [12](https://www.lfcs.inf.ed.ac.uk/reports/95/ECS-LFCS-95-317/). Approximate evaluation to a specified relative error is less well understood[12](https://www.lfcs.inf.ed.ac.uk/reports/95/ECS-LFCS-95-317/).
## History
[J. Howard Redfield](https://www.edgepedia.org/j-howard-redfield) published the underlying enumeration idea in 1927 in "The Theory of Group-Reduced Distributions" in the *American Journal of Mathematics*[3](https://www.jstor.org/stable/2370675). Pólya's 1937 paper, published in *Acta Mathematica* (volume 68, pages 145–254), developed the theory independently and applied it widely, and the associated theory is often called Pólya–Redfield theory[2](https://portal.mardi4nfdi.de/wiki/Publication%3A2645775) • [5](https://cayley.academic.csusb.edu/content/papers/dcj.pdf). The 1987 book *Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds* by Pólya and R. C. Read collects the paper's legacy, including a survey chapter "The Legacy of Pólya's Paper: Fifty Years of Pólya Theory"[13](https://link.springer.com/book/10.1007/978-1-4612-4664-0).
## References
1. [Polya Theory – The Cycle Index Polynomial, Stanford (B. Lynn)](https://crypto.stanford.edu/~blynn/polya/cycleindex.html)
2. [Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, G. Pólya, Acta Mathematica 68 (1937), MaRDI portal](https://portal.mardi4nfdi.de/wiki/Publication%3A2645775)
3. [The Theory of Group-Reduced Distributions, J. Howard Redfield, American Journal of Mathematics 49(3) (1927), JSTOR](https://www.jstor.org/stable/2370675)
4. [Automating Pólya Theory: The Computational Complexity of the Cycle Index Polynomial, Information and Computation 105(2) (1993)](https://www.sciencedirect.com/science/article/pii/S089054018371045X)
5. [Counting Sylow double cosets in the symmetric group, P. Renteln, Discrete Mathematics 347 (2024)](https://cayley.academic.csusb.edu/content/papers/dcj.pdf)
6. [Finite Permutation Groups – Category Framework, Sage documentation](https://doc.sagemath.org/html/en/reference/categories/sage/categories/finite_permutation_groups.html)
7. [Pólya theorem, Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/P%C3%B3lya_theorem)
8. [Affine equivalence of monomial rotation symmetric Boolean functions, Journal of Mathematical Cryptology](https://doi.org/10.1515/jmc-2016-0042)
9. [Polya Enumeration Theorem, MIT PRIMES (Fan, Zhu)](https://math.mit.edu/research/highschool/primes/materials/2018/conf/17-3%20Fan-ZhuS.pdf)
10. [An Introduction to Group Actions and Cycle Indices through the MacWilliams Identity, K. Imamura](https://www.koji-imamura.org/en/resources/notes/macwilliams-08)
11. [SYMMETRICA-MANUAL – Orbit-enumeration in SYMMETRICA](https://www.mathe2.uni-bayreuth.de/frib/html/symman/manual_20.html)
12. [Computational Polya Theory, LFCS report ECS-LFCS-95-317, University of Edinburgh](https://www.lfcs.inf.ed.ac.uk/reports/95/ECS-LFCS-95-317/)
13. [Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, G. Pólya and R. C. Read, Springer (1987)](https://link.springer.com/book/10.1007/978-1-4612-4664-0)
14. [Algebraic Combinatorics -- Cycle indicator polynomials](https://www.mathe2.uni-bayreuth.de/frib/html/book/hyl00_60.html)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Combinatorics › Enumerative combinatorics › Generating functions and symbolic methods › Pólya enumeration theorem*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license