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 A_n is the parity-filtered symmetric-group sum

Statement

For every integer $n \geq 2$ ,

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

Equivalently,

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

Facts & Assumptions

Given: an integer $n \geq 2$ .

[L1]

A permutation lies in $A_{n}$ exactly when it is even (The alternating group $A_{n} = \ker (sgn)$ of even permutations).

[L2]

A permutation with cycle counts $m_{d}$ has sign $(- 1)^{\sum_{d} (d - 1) m_{d}}$ (A $k$ -cycle has sign $(- 1)^{k - 1}$ , and $sgn (σ) = (- 1)^{n - c (σ)}$ when fixed points are counted as cycles).

[L3]

For $n \geq 2$ , the alternating group has half the elements of $S_{n}$ , so $∣ A_{n} ∣ = n! / 2$ ( $A_{n}$ is normal in $S_{n}$ ; for $n \geq 2$ , $2 ∣ A_{n} ∣ = n!$ , while $A_{n} = S_{n}$ for $n = 0, 1$ ).

[L4]

The symmetric-group cycle index is the sum over cycle types (The cycle index of S_n is the sum over cycle types).

Proof

technique · direct

1.1L1L2

By [L1] and [L2], a permutation of cycle type $(m_{1}, \dots, m_{n})$ belongs to $A_{n}$ exactly when $\sum_{d} (d - 1) m_{d}$ is even.

2.1step 1.1L4

For such an even cycle type, the number of permutations in $A_{n}$ with that type is the same as the number in $S_{n}$ , namely $n! / \prod_{d} d^{m_{d}} m_{d}!$ , because an entire cycle type is either even or odd. Therefore the unnormalized cycle-index sum over $A_{n}$ is $\sum_{\begin{array}{c} m_{1}, \dots, m_{n} \geq 0 \\ \sum_{d} d m_{d} = n \\ \sum_{d} (d - 1) m_{d} even \end{array}} \frac{n!}{\prod_{d} d^{m_{d}} m_{d}!} \prod_{d} s_{d}^{m_{d}}$ .

3.1step 2.1L3∎

Divide step 2.1 by $∣ A_{n} ∣ = n! / 2$ from [L3]. This multiplies the cycle-type coefficients by $2 / n!$ , leaving exactly $2 \sum_{\begin{array}{c} m_{1}, \dots, m_{n} \geq 0 \\ \sum_{d} d m_{d} = n \\ \sum_{d} (d - 1) m_{d} even \end{array}} \frac{1}{\prod_{d} d^{m_{d}} m_{d}!} \prod_{d} s_{d}^{m_{d}}$ . The equivalent filtered formula follows because $1 + (- 1)^{e}$ is $2$ when $e$ is even and $0$ when $e$ is odd.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

15 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

Eric W. Weisstein, Cycle Index, Wolfram MathWorld (standard reference, not scraped)