TheoremStatement: Literature-sourcedProof: Literature-sourcedaudited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The cycle index of S_n is the sum over cycle types

Statement

For every integer $n \geq 0$ ,

$Z (S_{n}) = \sum_{\begin{array}{c} m_{1}, \dots, m_{n} \geq 0 \\ \sum_{d = 1}^{n} d m_{d} = n \end{array}} \frac{1}{\prod_{d = 1}^{n} d^{m_{d}} m_{d}!} \prod_{d = 1}^{n} s_{d}^{m_{d}} .$

Facts & Assumptions

Given: an integer $n \geq 0$ .

[F1]

By definition, the cycle index averages the monomial $\prod_{d} s_{d}^{j_{d} (σ)}$ over all permutations $σ \in S_{n}$ (The cycle index of a finite permutation group).

[L1]

The number of permutations with fixed cycle type $(m_{1}, \dots, m_{n})$ is $n! / \prod_{d} d^{m_{d}} m_{d}!$ (Permutations with a fixed cycle type are counted by the standard factorial denominator).

Proof

technique · direct

1.1F1

In the average from [F1], all permutations with the same cycle type contribute the same monomial $\prod_{d} s_{d}^{m_{d}}$ . Thus the sum may be regrouped by cycle type.

2.1step 1.1L1

For a fixed cycle type $(m_{1}, \dots, m_{n})$ with $\sum_{d} d m_{d} = n$ , there are exactly the permutations counted by [L1]. Their total contribution to the unnormalized sum is therefore $\frac{n!}{\prod_{d} d^{m_{d}} m_{d}!} \prod_{d} s_{d}^{m_{d}}$ .

3.1step 2.1F1∎

Divide the regrouped sum of step 2.1 by $n!$ , as required by [F1]. The factor $n!$ cancels, leaving exactly the displayed cycle-type expansion for $Z (S_{n})$ .

Depends on

Used by

The symmetric-group cycle-index series is coefficientwise exponential Corollary
The cycle index of S₃ Example
The cycle index of Aₙ is the parity-filtered symmetric-group sum Theorem

Dependency tree · two levels

8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ben Lynn, Polya Theory: The Cycle Index Polynomial (standard reference, not scraped)
Eric W. Weisstein, Cycle Index, Wolfram MathWorld (standard reference, not scraped)