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.
Over a commutative -algebra, has generating function
Statement
Let be a combinatorial class with no size-zero objects, and write
Over a commutative -algebra,
Facts & Assumptions
Given: A combinatorial class with no size-zero objects and ordinary generating function .
Cauchy-Frobenius orbit counting: for a finite group action, (Cauchy-Frobenius orbit counting: for a finite group action).
If , then an -tuple fixed by rotation by places is equivalently a repetition of one block of length (A tuple fixed by a cyclic rotation is determined by a shorter periodic block).
For , Euler's totient is the number of unit classes in , and is a unit exactly when (The unit group and Euler's totient for , For , is a unit if and only if ).
The formal logarithm is (Formal exponential, logarithm, and binomial powers over a commutative -algebra).
Proof
For each , let be the class of cycles of length . Since every object of has positive size, an -tuple of total size can use only entries of size at most , so every size layer of is finite. Applying [L1] degree by degree to the cyclic action of therefore gives , where is the generating function of the -tuples fixed by rotation by places.
Put and . By [L2], a tuple fixed by rotation by is obtained by repeating one block of length . Each entry in that block is counted times in the full cycle, so the generating function of such fixed tuples is .
Fix a divisor of , and write . The rotations with are exactly the integers with and , so [L3] shows that there are of them. Step 1.2 therefore gives .
Summing step 2.1 over all and writing yields . Because , every degree receives contributions from only finitely many pairs , so this regrouping is coefficientwise finite.
Applying [L4] with gives . Substituting this into step 3.1 gives the stated cycle formula.
Depends on
- The cycle construction $\operatorname{CYC}(\mathcal{A})$
- A tuple fixed by a cyclic rotation is determined by a shorter periodic block
- Cauchy-Frobenius orbit counting: $|G|\,|X/G|=\sum_{g\in G}|X^g|$ for a finite group action
- The unit group $(\mathbb{Z}/n)^\times$ and Euler's totient $\varphi(n)=\lvert(\mathbb{Z}/n)^\times\rvert$ for $n\ge1$
- For $n\ge1$, $[a]_n$ is a unit if and only if $\gcd(a,n)=1$
- Formal exponential, logarithm, and binomial powers over a commutative $\mathbb Q$-algebra
- Formal $\exp$ and $\log$ are inverse homomorphisms and formal binomial powers obey the expected addition laws
Used by
Dependency tree · two levels
35 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
- Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics (standard reference, not scraped)
- Stephen Melczer, An Invitation to Enumeration, Chapter 5: Combinatorial Constructions (standard reference, not scraped)