LemmaStatement: Literature-sourcedProof: Literature-sourcedSession-authored (Fable 5 assisted)audited 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.

Permutations with a fixed cycle type are counted by the standard factorial denominator

Statement

Let $m_{1}, \dots, m_{n}$ be nonnegative integers satisfying

$\sum_{d = 1}^{n} d m_{d} = n .$

Then the number of permutations in $S_{n}$ with exactly $m_{d}$ cycles of length $d$ for each $d$ is

$\frac{n!}{\prod_{d = 1}^{n} d^{m_{d}} m_{d}!} .$

Facts & Assumptions

Given: nonnegative integers $m_{1}, \dots, m_{n}$ with $\sum_{d} d m_{d} = n$ .

[A1]

A permutation of the set ${1, \dots, n}$ has the stated cycle type when it has exactly $m_{d}$ cycles of length $d$ for each $d$ .

Proof

technique · direct

1.1

Arrange the symbols $1, \dots, n$ in a line. There are $n!$ such linearisations. Break the line into consecutive blocks: first the $m_{1}$ blocks of length $1$ , then the $m_{2}$ blocks of length $2$ , and so on, ending with the $m_{n}$ blocks of length $n$ . Turn each block $(a_{1}, \dots, a_{d})$ into the cycle $(a_{1} a_{2} \dots a_{d})$ . This produces a permutation of the required cycle type.

A1construct

2.1

Every permutation of that cycle type is produced many times by step 1.1. For each $d$ -cycle, any of its $d$ cyclic rotations gives the same cycle, so each such cycle is counted $d$ times. Also, the $m_{d}$ cycles of the same length may be listed in any order, so they are counted a further factor of $m_{d}!$ . Therefore each permutation is produced exactly $\prod_{d} d^{m_{d}} m_{d}!$ times.

step 1.1

3.1

Divide the total number $n!$ of linearisations from step 1.1 by the overcounting factor of step 2.1. This gives exactly $\frac{n!}{\prod_{d = 1}^{n} d^{m_{d}} m_{d}!}$ .

step 1.1step 2.1∎

Depends on

Used by

Dependency tree · two levels

18 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)