Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-26
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 Q-algebra, CYC(A) has generating function k1φ(k)klog11A(xk)

Statement

Let A be a combinatorial class with no size-zero objects, and write

A(x)=n1anxn.

Over a commutative Q-algebra,

OGF(CYC(A))=k1φ(k)klog11A(xk).

Facts & Assumptions

Given: A combinatorial class A with no size-zero objects and ordinary generating function A(x).

[L1]

Cauchy-Frobenius orbit counting: for a finite group action, GX/G=gGXg (Cauchy-Frobenius orbit counting: GX/G=gGXg for a finite group action).

[L2]

If d=gcd(m,r), then an m-tuple fixed by rotation by r places is equivalently a repetition of one block of length d (A tuple fixed by a cyclic rotation is determined by a shorter periodic block).

[L3]

For k1, Euler's totient φ(k) is the number of unit classes in Z/k, and [s]k is a unit exactly when gcd(s,k)=1 (The unit group (Z/n)× and Euler's totient φ(n)=(Z/n)× for n1, For n1, [a]n is a unit if and only if gcd(a,n)=1).

[L4]

The formal logarithm is log(1+u)=j1(1)j1uj/j (Formal exponential, logarithm, and binomial powers over a commutative Q-algebra).

Proof

technique · direct
1.1

For each m1, let Cm be the class of cycles of length m. Since every object of A has positive size, an m-tuple of total size n can use only entries of size at most n, so every size layer of Am is finite. Applying [L1] degree by degree to the cyclic action of Cm therefore gives OGF(Cm)=(1/m)r=0m1Fm,r(x), where Fm,r(x) is the generating function of the m-tuples fixed by rotation by r places.

L1
1.2

Put d:=gcd(m,r) and k:=m/d. By [L2], a tuple fixed by rotation by r is obtained by repeating one block of length d. Each entry in that block is counted k times in the full cycle, so the generating function of such fixed tuples is Fm,r(x)=A(xk)d=A(xm/d)d.

L2
2.1

Fix a divisor k of m, and write d=m/k. The rotations with m/gcd(m,r)=k are exactly the integers r=ds with 0s<k and gcd(s,k)=1, so [L3] shows that there are φ(k) of them. Step 1.2 therefore gives OGF(Cm)=(1/m)kmφ(k)A(xk)m/k.

step 1.2L3algebra
3.1

Summing step 2.1 over all m1 and writing m=dk yields OGF(CYC(A))=k1(φ(k)/k)d1A(xk)d/d. Because A(0)=0, every degree receives contributions from only finitely many pairs (k,d), so this regrouping is coefficientwise finite.

step 2.1algebra
4.1

Applying [L4] with u=A(xk) gives d1A(xk)d/d=log(1/(1A(xk))). Substituting this into step 3.1 gives the stated cycle formula.

step 3.1L4

Depends on

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