Cycle index
In combinatorial mathematics, the cycle index of a permutation group G acting on a finite set \Omega of size n is defined as the polynomial Z(G) = \frac{1}{|G|} \sum_{g \in G} \prod_{i=1}^n s_i^{c_i(g)}, where c_i(g) denotes the number of cycles of length i in the cycle decomposition of the permutation g, and s_1, \dots, s_n are indeterminates.[1] This polynomial serves as a generating function that encodes the average cycle structure of elements in G, providing a compact summary of the group's permutation properties.[2] The concept was introduced by George Pólya in his seminal 1937 paper on combinatorial enumeration, where it forms the core of the Pólya enumeration theorem (also known as the Redfield–Pólya theorem).[3] This theorem uses the cycle index to count the number of distinct colorings or labelings of a set up to the symmetries imposed by G; specifically, substituting r for each s_i yields the number of inequivalent r-colorings fixed by the group action.[2] For instance, in the case of the cyclic group \mathbb{Z}_n, the cycle index simplifies to \frac{1}{n} \sum_{d \mid n} \phi(d) x_d^{n/d}, where \phi is Euler's totient function, facilitating explicit computations for rotational symmetries.[1] Cycle indices find broad applications across combinatorics and related fields. In chemistry, they enumerate molecular isomers under symmetry groups like the dihedral group for ring structures, such as determining the six distinct xylenol isomers from benzene derivatives with one hydroxyl and two methyl groups.[4] In graph theory, they count non-isomorphic graphs on n vertices by applying the cycle index to the pair group of potential edges, yielding, for example, 11 unlabeled graphs on four vertices.[4] Additional uses include coding theory, where the cycle index of a code's permutation group relates directly to its weight enumerator for error-correcting properties over finite fields,[1] and even music theory, for counting distinct musical scales modulo transpositions via cyclic groups.[4] These tools extend to more advanced settings, such as cycle indices for finite classical groups in random matrix theory and representation theory.[5]Prerequisites
Permutation Groups and Actions
A permutation is defined as a bijective function from a finite set to itself, rearranging the elements of the set while preserving the set's structure.[6] The collection of all such permutations on a set with n elements forms a group under the operation of function composition, known as the symmetric group S_n, which has order n!.[7] A group action arises when a group G operates on a set X through permutations, meaning there is a homomorphism from G to the symmetric group on X, where each group element corresponds to a permutation of X.[8] For any element x \in X, the orbit of x is the set of all images under the action, and the stabilizer of x is the subgroup fixing x; the orbit-stabilizer theorem states that the size of the orbit times the size of the stabilizer equals the order of G.[9] This theorem quantifies the relationship between symmetry and fixed points, essential for enumeration tasks. Among group actions, a faithful action occurs when distinct group elements induce distinct permutations on X, ensuring the action is injective as a homomorphism.[8] A regular action, such as the left multiplication of G on itself, is both faithful and transitive, with every stabilizer trivial and every orbit the entire set.[10] These action types are particularly relevant in enumeration, as they model symmetries without redundancy or incomplete coverage. The foundational concepts of permutation groups and actions trace their origins to early 20th-century group theory, notably through William Burnside's work on counting distinct objects under group symmetries.[11] Burnside's contributions, building on earlier ideas, emphasized these tools for solving combinatorial problems invariant under group operations.Cycle Decomposition of Permutations
Every permutation of a finite set can be expressed uniquely as a product of disjoint cycles, up to the order of the cycles and the starting point within each cycle.[12] This decomposition arises because the orbits under the action of the permutation partition the set into cycles, where each cycle represents a closed loop of elements mapped successively by the permutation.[13] In disjoint cycle notation, a permutation \sigma \in S_n is written as a product \sigma = (a_1\ a_2\ \dots\ a_k)(b_1\ b_2\ \dots\ b_m) \cdots, where the cycles are disjoint (no shared elements) and the notation (a_1\ a_2\ \dots\ a_k) indicates that \sigma(a_1) = a_2, \sigma(a_2) = a_3, ..., \sigma(a_k) = a_1. For example, in S_5, the permutation \sigma defined by \sigma(1)=2, \sigma(2)=1, \sigma(3)=4, \sigma(4)=5, \sigma(5)=3 is denoted as (1\ 2)(3\ 4\ 5).[13] Cycles are conventionally written starting with their smallest element and ordered by increasing smallest element for standardization.[14] The cycle type of a permutation is the partition of n given by the lengths of its cycles in the decomposition, often written in decreasing order (e.g., the type $3+2 for cycles of lengths 3 and 2, or $2+2+1 for two 2-cycles and a fixed point).[15] Fixed points—elements i where \sigma(i) = i—correspond to 1-cycles, which are typically omitted from the notation for brevity, as they do not affect the permutation's action on other elements. For instance, the identity permutation in S_5 has cycle type $1+1+1+1+1 but is denoted simply as the empty product or e.[13] In the symmetric group S_n, two permutations are conjugate if and only if they have the same cycle type; thus, conjugacy classes are precisely the sets of permutations sharing a given cycle type.[16] This classification is fundamental, as the number of conjugacy classes in S_n equals the number of integer partitions of n.[15] To compute the cycle decomposition from the two-row notation of a permutation (where the top row is $1, 2, \dots, n and the bottom is \sigma(1), \sigma(2), \dots, \sigma(n)) or from its permutation matrix (with 1 at position (i, \sigma(i))), apply the following algorithm: Begin with the smallest unused element i; form a cycle by repeatedly applying \sigma (following the bottom row or matrix column) until returning to i; then repeat with the next unused element until all are covered.[13] This process yields the disjoint cycles directly, ensuring the decomposition is obtained efficiently in O(n) steps.[12]Definition and Properties
Formal Definition
The cycle index of a finite permutation group G acting on a finite set of n elements is the polynomial Z_G(x_1, x_2, \dots, x_n) = \frac{1}{|G|} \sum_{g \in G} \prod_{k=1}^n x_k^{c_k(g)}, where c_k(g) is the number of cycles of length k in the disjoint cycle decomposition of the permutation g \in G.[17] The variables x_k act as indeterminates that encode the contribution of cycles of length k, allowing the polynomial to capture the overall cycle structure across all group elements. In the specific case of the symmetric group S_n acting on the set = \{1, 2, \dots, n\} by permutation, the cycle index Z_{S_n}(x_1, x_2, \dots, x_n) averages the cycle type monomials over all n! permutations, providing a complete invariant for the cycle structures in S_n. This polynomial is homogeneous of total degree n, as the cycle lengths in any permutation g satisfy \sum_{k=1}^n k \cdot c_k(g) = n.[17] Moreover, the cycle index is invariant under group conjugation, since conjugate permutations share the same cycle type and thus the same monomial \prod_{k=1}^n x_k^{c_k(g)}. Substituting x_k = 1 for all k yields Z_G(1, 1, \dots, 1) = 1, which aligns with Burnside's lemma by giving the number of orbits (equal to 1) for the trivial action or one-color enumeration case, where every group element fixes all configurations.[17]Generating Function Interpretation
The cycle index of a permutation group G acting on a finite set serves as a multivariate generating function that encodes the cycle structures of its elements. Formally, it is the average of monomials tracking these structures: Z_G(x_1, x_2, \dots ) = \frac{1}{|G|} \sum_{g \in G} \prod_{k \geq 1} x_k^{c_k(g)}, where c_k(g) is the number of cycles of length k in the cycle decomposition of g. Each monomial \prod_k x_k^{c_k(g)} records the cycle type of g, and averaging over the group yields a polynomial that summarizes the overall distribution of cycle types within G. This algebraic structure facilitates the analysis of symmetries in combinatorial objects acted upon by G.[18] A central feature of this generating function is the substitution principle, which enables the enumeration of orbits under the group action by replacing the variables x_k according to the generating function of the structures assigned to cycles. For instance, substituting x_k with s^k, where s is a single indeterminate marking cycle lengths, produces Z_G(s, s^2, s^3, \dots ) = s^n for an action on a set of size n, reflecting the fixed total length across all permutations. More generally, this principle underlies Pólya's enumeration theorem, where substitutions like x_k \mapsto f(s^k) (with f the generating function for cycle components) yield the generating function for the number of distinct orbits, such as colorings or graphs up to symmetry. In combinatorial species theory, the cycle index connects directly to exponential generating functions, providing a bridge between labeled and unlabeled structures. The cycle index series of a species F, extended to variable size, is Z_F(p_1, p_2, \dots ; x) = \sum_{n \geq 0} \frac{x^n}{n!} \sum_{g \in S_n} |F()^g| \prod_k p_k^{c_k(g)}. Substituting p_k = 0 for k > 1 and p_1 = 1 recovers the exponential generating function for labeled F-structures, \sum |F()| \frac{x^n}{n!}, while setting all p_k = 1 yields the ordinary generating function for unlabeled structures, \sum a_n x^n where a_n counts isomorphism classes. This highlights the cycle index's role in capturing symmetries via cycle-pointing in species compositions.[18] The cycle index relates to monomial symmetric functions through its expansion as a weighted sum over cycle types. Specifically, Z_G expresses the average cycle type as \sum_{\lambda \vdash n} \left( \frac{|\{g \in G : \text{cycle type of } g = \lambda\}|}{|G|} \right) m_{\lambda}(x_1, x_2, \dots ), where m_{\lambda} is the monomial symmetric function corresponding to partition \lambda = (1^{c_1} 2^{c_2} \dots ), and the variables x_k play the role of indeterminates for cycle lengths. This representation underscores the cycle index's position within the ring of symmetric functions, facilitating transformations like plethystic substitutions for advanced enumerative purposes.[19] The cycle index Z_G uniquely generates the cycle types of permutations in G, weighted by their average frequency \frac{1}{|G|} \sum_{g \in G} \mathbf{1}_{\text{type}(g) = \lambda} for each type \lambda. This uniqueness arises from its construction via the Reynolds operator (group averaging), ensuring invariance under relabeling of cycles of equal length while faithfully reproducing the empirical distribution of types in G.[20]Computation Examples
Basic Example
A basic example of the cycle index arises from the action of the cyclic group C_3 of order 3 on a set of three elements, such as beads arranged in a triangular necklace under rotation.[21] The group C_3 consists of three elements: the identity permutation, which decomposes into three 1-cycles and contributes the monomial x_1^3; a rotation by 120°, which is a single 3-cycle and contributes x_3; and a rotation by 240°, which is also a single 3-cycle and contributes x_3.[22] To compute the cycle index, form the monomial for each group element based on its cycle type and average over the group order:Z_{C_3}(x_1, x_2, x_3) = \frac{1}{3} \left( x_1^3 + x_3 + x_3 \right) = \frac{1}{3} \left( x_1^3 + 2 x_3 \right). [21] This cycle index can be used to enumerate distinct colorings up to symmetry via the Pólya enumeration theorem; for instance, with c available colors, substitute x_k = c for each k, yielding \frac{1}{3} (c^3 + 2c), which counts the number of inequivalent necklaces under rotation.[21]
Edge Permutations of Complete Graphs
The edge permutation group of the complete graph K_n is induced by the natural action of the symmetric group S_n on the vertices, which permutes the \binom{n}{2} edges as unordered pairs. For small n, the cycle index of this action can be computed by determining the cycle structure on the edges for each conjugacy class of permutations in S_n. Consider K_3, the triangle with 3 vertices and 3 edges. The group S_3 has order 6 and acts on the edges labeled, say, e_{12} = \{1,2\}, e_{13} = \{1,3\}, e_{23} = \{2,3\}.- The identity permutation fixes all 3 edges, contributing the monomial x_1^3.
- There are 3 transpositions, such as (1\,2). This fixes e_{12} (as a 1-cycle) and swaps e_{13} with e_{23} (a 2-cycle), yielding x_1 x_2.
- There are 2 three-cycles, such as (1\,2\,3). This cycles all three edges: e_{12} \to e_{23} \to e_{13} \to e_{12}, yielding x_3.
- The identity (1 element, type $1^4) fixes all 6 edges: x_1^6.
- Transpositions (6 elements, type $2,1^2), e.g., (1\,2): fixes e_{12} and e_{34} (two 1-cycles); swaps e_{13} \leftrightarrow e_{23} and e_{14} \leftrightarrow e_{24} (two 2-cycles): x_1^2 x_2^2.
- Double transpositions (3 elements, type $2^2), e.g., (1\,2)(3\,4): fixes e_{12} and e_{34} (two 1-cycles); swaps e_{13} \leftrightarrow e_{24} and e_{14} \leftrightarrow e_{23} (two 2-cycles): x_1^2 x_2^2.
- Three-cycles (8 elements, type $3,1), e.g., (1\,2\,3): cycles e_{12} \to e_{23} \to e_{13} \to e_{12} (one 3-cycle) and e_{14} \to e_{24} \to e_{34} \to e_{14} (one 3-cycle): x_3^2.
- Four-cycles (6 elements, type $4), e.g., (1\,2\,3\,4): cycles the boundary edges e_{12} \to e_{23} \to e_{34} \to e_{41} \to e_{12} (one 4-cycle); swaps the diagonals e_{13} \leftrightarrow e_{24} (one 2-cycle): x_2 x_4.