Session-authored (Fable 5 assisted)

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.

✓ 29 results · all verified · 20 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 9 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Combinatorial Classes and the Symbolic Method

1 · Prerequisites

2 · Summary

Formal power series, coefficient extraction, summable families, composition, differentiation, and the $x$ -adic topology supply the exact background for this development. Finite cardinality underlies the counting sequence of a class, the published stars-and-bars theorem recovers the fixed-part composition count, and Euler's totient together with Burnside's orbit count is the seam that makes the cycle construction and the necklace formula rigorous.

The page defines combinatorial classes and the basic constructors $E$ , $Z$ , $+$ , $\times$ , $SEQ$ , $MSET$ , $PSET$ , $CYC$ , substitution, and pointing, then proves their ordinary generating-function translations. From those rules it derives binary words, compositions, partitions, necklaces, and the functional equations for plane and binary trees. It closes with order-raising recursive specifications, where $x$ -adic completeness yields unique fixed points for symbolic recursive equations.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Combinatorial classes, counting sequences and ordinary generating functions

Definition

A combinatorial class is a pair $(A, ∣ \cdot ∣)$ consisting of a set $A$ and a size map $∣ \cdot ∣ : A \to N$ such that, for every $n \in N$ , the level

$A_{n} : = {a \in A : ∣ a ∣ = n}$

is finite (The cardinality $∣ A ∣$ of a finite set).

The counting sequence of $A$ is

$a_{n} : = ∣ A_{n} ∣ (n \in N),$

Viewing each natural coefficient $a_{n}$ as its canonical integer by The naturals embed in the integers, its ordinary generating function is the formal power series

$A (x) : = \sum_{n \geq 0} a_{n} x^{n} \in Z ⟦ x ⟧$

in the sense of Formal power series over a commutative ring and the coefficient-extraction functional $[x^{n}]$ .

An isomorphism of combinatorial classes $A \to B$ is a bijection $f : A \to B$ such that $∣ f (a) ∣ = ∣ a ∣$ for every $a \in A$ . Such a bijection identifies each level $A_{n}$ with the corresponding level $B_{n}$ , so isomorphic classes have the same counting sequence and the same ordinary generating function.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

The neutral class $E$ and the atomic class $Z$

Definition

The neutral class $E$ has one object $ϵ$ of size $0$ and no objects of any other size. Its counting sequence is $1, 0, 0, \dots$ , so its ordinary generating function is $1$ .

The atomic class $Z$ has one object $z$ of size $1$ and no objects of any other size. Its counting sequence is $0, 1, 0, 0, \dots$ , so its ordinary generating function is $x$ .

Both are combinatorial classes in the sense of Combinatorial classes, counting sequences and ordinary generating functions.

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-08-26Open item page →

Disjoint unions and Cartesian products of combinatorial classes

Definition

Let $A$ and $B$ be combinatorial classes.

Their disjoint union $A + B$ is the tagged union

$A + B : = ({0} \times A) \cup ({1} \times B),$

with size $∣ (0, a) ∣ : = ∣ a ∣$ and $∣ (1, b) ∣ : = ∣ b ∣$ . The tags are part of the data: they keep the two copies disjoint even when $A$ and $B$ have common underlying objects.

Their Cartesian product $A \times B$ is the set of ordered pairs $(a, b)$ with $a \in A$ and $b \in B$ , equipped with the size map

$∣ (a, b) ∣ : = ∣ a ∣ + ∣ b ∣ .$

Here the ordered pair itself records both components. This uniqueness of the factorisation is part of the construction: later counterexamples show that dropping it breaks the product rule.

For later shorthand, $m A$ means the disjoint union of $m$ tagged copies of $A$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Disjoint union and Cartesian product translate to addition and multiplication of ordinary generating functions

Statement

Let $A$ and $B$ be combinatorial classes with ordinary generating functions

$A (x) = \sum_{n \geq 0} a_{n} x^{n}, B (x) = \sum_{n \geq 0} b_{n} x^{n} .$

Then the disjoint union and Cartesian product of Disjoint unions and Cartesian products of combinatorial classes satisfy

$OGF (A + B) = A (x) + B (x),$

and

$OGF (A \times B) = A (x) B (x) .$

Facts & Assumptions

Given: Combinatorial classes $A$ and $B$ with counting sequences $(a_{n})$ and $(b_{n})$ and ordinary generating functions $A (x)$ and $B (x)$ .

[L1]

If $I$ is a finite set and $(A_{i})_{i \in I}$ is a family of finite sets that are pairwise disjoint, then $⋃_{i \in I} A_{i}$ is finite and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ (The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition).

[L2]

If $A$ and $B$ are finite then $A \times B$ is finite and $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ (The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ ).

[L3]

For formal power series, $[x^{n}] (F G) = \sum_{i = 0}^{n} [x^{i}] F [x^{n - i}] G$ (Formal power series over a commutative ring and the coefficient-extraction functional $[x^{n}]$ ).

Proof

technique · direct

1.1

For each $n \in N$ , the size- $n$ layer of $A + B$ is the disjoint union of the tagged finite sets $A_{n}$ and $B_{n}$ , so it has cardinality $a_{n} + b_{n}$ .

1.2

For each $n \in N$ , the size- $n$ layer of $A \times B$ is the disjoint union of the finite sets $A_{i} \times B_{n - i}$ for $0 \leq i \leq n$ , so its cardinality is $\sum_{i = 0}^{n} a_{i} b_{n - i}$ .

L1L2

2.1

Step 1.1 says $[x^{n}] OGF (A + B) = a_{n} + b_{n} = [x^{n}] (A (x) + B (x))$ , and step 1.2 together with [L3] says $[x^{n}] OGF (A \times B) = \sum_{i = 0}^{n} a_{i} b_{n - i} = [x^{n}] (A (x) B (x))$ . Equality of coefficients in every degree proves both displayed identities.

step 1.1step 1.2L3∎

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

The sequence construction $SEQ (A)$

Definition

Let $A$ be a combinatorial class. Its sequence construction $SEQ (A)$ is the class of all finite ordered sequences

$σ = (a_{1}, \dots, a_{r}) (r \geq 0, a_{i} \in A),$

with size

$∣ σ ∣ : = ∣ a_{1} ∣ + \dots + ∣ a_{r} ∣ .$

The case $r = 0$ is the empty sequence, whose size is $0$ ; it is the unique object of the neutral class $E$ .

Write ${SEQ}_{\geq 1} (A)$ for the subclass of nonempty sequences.

If $A$ has an object of size $0$ , then $SEQ (A)$ need not be a combinatorial class: infinitely many different lengths can produce the same total size. The generating-function theorem therefore carries a no-size-zero hypothesis.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$

Statement

Let $A$ be a combinatorial class with ordinary generating function

$A (x) = \sum_{n \geq 0} a_{n} x^{n},$

and suppose $A$ has no size-zero objects, so $a_{0} = 0$ . Then $SEQ (A)$ is a combinatorial class and

$OGF (SEQ (A)) = \frac{1}{1 - A (x)} .$

Consequently,

$OGF ({SEQ}_{\geq 1} (A)) = \frac{A (x)}{1 - A (x)} .$

Facts & Assumptions

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

[L1]

Disjoint union and Cartesian product translate to addition and multiplication of ordinary generating functions (Disjoint union and Cartesian product translate to addition and multiplication of ordinary generating functions).

[L2]

A formal power series is a unit exactly when its constant coefficient is a unit (A formal power series is a unit exactly when its constant coefficient is a unit).

Proof

technique · direct

1.1

Every sequence in $SEQ (A)$ is either empty or has the form $(a, σ)$ with $a \in A$ and $σ \in SEQ (A)$ , so $SEQ (A) = E + A \times SEQ (A)$ as combinatorial classes. Also, because every object of $A$ has positive size, a sequence of total size $n$ has length at most $n$ , so the size- $n$ layer of $SEQ (A)$ is finite.

construct

2.1

Let $F (x)$ be the ordinary generating function of $SEQ (A)$ . Step 1.1 and [L1] give $F (x) = 1 + A (x) F (x)$ .

step 1.1L1

3.1

Since $A$ has no size-zero objects, the constant coefficient of $A (x)$ is $0$ , so the constant coefficient of $1 - A (x)$ is $1$ , which is a unit. By [L2], $1 - A (x)$ is invertible, and solving the equation of step 2.1 gives $F (x) = 1 / (1 - A (x))$ .

step 2.1L2

4.1

The class ${SEQ}_{\geq 1} (A)$ is $SEQ (A) - E$ , so [L1] and step 3.1 give $OGF ({SEQ}_{\geq 1} (A)) = F (x) - 1 = A (x) / (1 - A (x))$ .

step 3.1L1∎

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-26Open item page →

Binary words have generating function $1 / (1 - 2 x)$

Statement

Let $B$ be the class of finite binary words, with size equal to word length. Then

$OGF (B) = \frac{1}{1 - 2 x} .$

Facts & Assumptions

Given: Two disjoint copies $Z_{0}$ and $Z_{1}$ of the atomic class $Z$ , and the class $A : = Z_{0} + Z_{1}$ .

[L1]

[L2]

If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$ (If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$ ).

Proof

technique · direct

1.1

Each of $Z_{0}$ and $Z_{1}$ has generating function $x$ , so $A$ has generating function $x + x = 2 x$ by [L1]. A binary word is exactly a finite sequence of objects from $A$ .

2.1

The class $A$ has no size-zero objects, so [L2] applies and gives $OGF (B) = OGF (SEQ (A)) = 1 / (1 - 2 x)$ .

step 1.1L2∎

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Positive-integer compositions have generating function $x / (1 - 2 x)$

Statement

Let $C$ be the class of compositions of positive integers, with size equal to the sum of the parts. Then

$OGF (C) = \frac{x}{1 - 2 x} .$

Facts & Assumptions

Given: The atomic class $Z$ and the constructions $SEQ (Z)$ and ${SEQ}_{\geq 1} (Z)$ .

[L1]

If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$ , and ${SEQ}_{\geq 1} (A)$ has generating function $A (x) / (1 - A (x))$ (If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$ ).

[L2]

Proof

technique · direct

1.1

Let $P : = {SEQ}_{\geq 1} (Z)$ . Since $OGF (Z) = x$ , [L1] gives $OGF (P) = x / (1 - x)$ . An object of $P$ is a nonempty sequence of atoms, so it records one positive integer, namely its length.

2.1

A composition is a nonempty sequence of such positive-size blocks, so $C = {SEQ}_{\geq 1} (P)$ . Applying [L1] again gives $OGF (C) = OGF (P) / (1 - OGF (P)) = (x / (1 - x)) / (1 - x / (1 - x)) = x / (1 - 2 x)$ .

step 1.1L1L2algebra∎

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Compositions of $n$ into $k$ positive parts are counted by $(\binom{n - 1}{k - 1})$

Statement

Let $n, k \in N$ with $n \geq 1$ and $k \geq 1$ . Then the number of compositions of $n$ into exactly $k$ positive parts is

$(\binom{n - 1}{k - 1}) .$

When $k > n$ , there are no such compositions.

Facts & Assumptions

Given: Naturals $n \geq 1$ and $k \geq 1$ .

[L1]

The previous corollary identifies a composition as a finite sequence of positive integers (Positive-integer compositions have generating function $x / (1 - 2 x)$ ).

[L2]

For $m \geq 1$ , the number of weak compositions of $N$ into $m$ parts is $(\binom{N + m - 1}{m - 1})$ (For $m \geq 1$ the number of weak compositions of $n$ into $m$ parts is $(\binom{n + m - 1}{m - 1})$ , and the number of compositions is $(\binom{n - 1}{m - 1})$ for $n \geq 1$ ).

Proof

technique · direct

1.1

A composition $(c_{1}, \dots, c_{k})$ of $n$ into $k$ positive parts determines a weak composition $(c_{1} - 1, \dots, c_{k} - 1)$ of $n - k$ into $k$ parts, and conversely adding $1$ to every part of a weak composition of $n - k$ into $k$ parts recovers a composition of $n$ into $k$ parts. If $k > n$ , no such composition exists, because $c_{1} + \dots + c_{k} \geq 1 + \dots + 1 = k > n$ .

L1constructalgebra

2.1

When $k \leq n$ , step 1.1 and [L2] give $(\binom{(n - k) + k - 1}{k - 1}) = (\binom{n - 1}{k - 1})$ compositions. Together with the empty case from step 1.1, this proves the claim.

step 1.1L2algebra∎

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

The multiset construction $MSET (A)$ and the powerset construction $PSET (A)$

Definition

Let $A$ be a combinatorial class.

An object of $MSET (A)$ is a finitely supported multiplicity function

$m : A \to N,$

whose value $m (a)$ records how many copies of $a$ occur. Its size is

$∣ m ∣ : = \sum_{a \in A} m (a) ∣ a ∣,$

which is a finite sum because the support of $m$ is finite.

An object of $PSET (A)$ is such a multiplicity function with values only in ${0, 1}$ , so it records an ordinary finite subset of $A$ . Its size is given by the same formula.

If $A$ has a size-zero object, then $MSET (A)$ may fail to be a combinatorial class because that object can be repeated arbitrarily often without changing total size. The powerset construction has no such failure: its multiplicities are only $0$ and $1$ , and the size-zero level of $A$ is finite. Its generating function would, however, acquire the extra factor $2^{a_{0}}$ . The product formulas below use the uniform no-size-zero hypothesis and therefore start at positive sizes.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

If $A$ has no size-zero objects then $MSET (A)$ has generating function $\prod_{n \geq 1} (1 - x^{n})^{- a_{n}}$

Statement

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

$A (x) = \sum_{n \geq 1} a_{n} x^{n}$

for its ordinary generating function. Then $MSET (A)$ is a combinatorial class and

$OGF (MSET (A)) = \prod_{n \geq 1} (1 - x^{n})^{- a_{n}} .$

Facts & Assumptions

Given: A combinatorial class $A$ with no size-zero objects and counting sequence $(a_{n})_{n \geq 1}$ .

[L1]

A formal power series is a unit exactly when its constant coefficient is a unit (A formal power series is a unit exactly when its constant coefficient is a unit).

[L2]

Summable formal families may be regrouped and rearranged, distribute over multiplication, and have well-defined locally finite products (Summable formal families may be regrouped and rearranged, distribute over multiplication, and have well-defined locally finite products).

Proof

technique · direct

1.1

For one fixed object $u \in A$ of size $n \geq 1$ , the possible multiplicities $0, 1, 2, \dots$ contribute the formal series $1 + x^{n} + x^{2 n} + \dots$ , which is $(1 - x^{n})^{- 1}$ because its product with $1 - x^{n}$ is $1$ coefficientwise. The factor exists by [L1], since $1 - x^{n}$ has constant coefficient $1$ .

L1algebra

2.1

A multiset of $A$ is exactly a choice of one multiplicity for each object of $A$ . Because every object has positive size, only finitely many objects can contribute to any fixed degree $< N$ , so the product of the per-object series of step 1.1 is locally finite and may be regrouped by [L2]. This also shows that each size layer of $MSET (A)$ is finite.

step 1.1L2

3.1

Regroup the factors of step 2.1 by object size. For each $n \geq 1$ there are exactly $a_{n}$ objects of size $n$ , and each contributes one factor $(1 - x^{n})^{- 1}$ , so the total contribution of size $n$ objects is $(1 - x^{n})^{- a_{n}}$ . Multiplying over all sizes gives the displayed product formula.

step 2.1L2∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26Open item page →

Over a commutative $Q$ -algebra, $MSET (A)$ has generating function $\exp (\sum_{k \geq 1} A (x^{k}) / k)$

Statement

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

$A (x) = \sum_{n \geq 1} a_{n} x^{n}$

be its ordinary generating function. Over a commutative $Q$ -algebra,

$OGF (MSET (A)) = \exp (\sum_{k \geq 1} \frac{A (x^{k})}{k}) .$

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[L1]

If $A$ has no size-zero objects then $OGF (MSET (A)) = \prod_{n \geq 1} (1 - x^{n})^{- a_{n}}$ (If $A$ has no size-zero objects then $MSET (A)$ has generating function $\prod_{n \geq 1} (1 - x^{n})^{- a_{n}}$ ).

[L2]

Formal $\exp$ and $\log$ are inverse homomorphisms, and $\log ((1 + u) (1 + v)) = \log (1 + u) + \log (1 + v)$ (Formal $\exp$ and $\log$ are inverse homomorphisms and formal binomial powers obey the expected addition laws).

[L3]

The formal logarithm is $\log (1 + u) = \sum_{j \geq 1} (- 1)^{j - 1} u^{j} / j$ (Formal exponential, logarithm, and binomial powers over a commutative $Q$ -algebra).

Proof

technique · direct

1.1

Let $M (x)$ denote the multiset generating function. By [L1], $M (x) = \prod_{n \geq 1} (1 - x^{n})^{- a_{n}}$ , so applying $\log$ and using [L2] gives $\log M (x) = \sum_{n \geq 1} - a_{n} \log (1 - x^{n})$ .

L1L2

2.1

By [L3], $- \log (1 - x^{n}) = \sum_{k \geq 1} x^{n k} / k$ , so $\log M (x) = \sum_{n \geq 1} \sum_{k \geq 1} a_{n} x^{n k} / k = \sum_{k \geq 1} (1 / k) \sum_{n \geq 1} a_{n} (x^{k})^{n} = \sum_{k \geq 1} A (x^{k}) / k$ . For each fixed degree, only finitely many pairs $(n, k)$ contribute, so the rearrangement is coefficientwise finite.

step 1.1L3algebra

3.1

Exponentiating the identity of step 2.1 and using that $\exp$ and $\log$ are inverse maps by [L2] gives $M (x) = \exp (\sum_{k \geq 1} A (x^{k}) / k)$ .

step 2.1L2∎

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Integer partitions have generating function $\prod_{n \geq 1} (1 - x^{n})^{- 1}$

Statement

Let $P$ be the class of integer partitions, with size equal to the sum of the parts. Then

$OGF (P) = \prod_{n \geq 1} (1 - x^{n})^{- 1} .$

Facts & Assumptions

Given: For each $n \geq 1$ , a single abstract object $p_{n}$ of size $n$ , and the combinatorial class $U : = {p_{1}, p_{2}, \dots}$ .

[L1]

Proof

technique · direct

1.1

A multiset of objects from $U$ records exactly an integer partition: the multiplicity of $p_{n}$ is the number of parts equal to $n$ , and the total size is the sum of the parts. Also $U$ has exactly one object of each positive size and none of size $0$ .

construct

2.1

Applying [L1] with $a_{n} = 1$ for every $n \geq 1$ gives $OGF (P) = \prod_{n \geq 1} (1 - x^{n})^{- 1}$ .

step 1.1L1∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

If $A$ has no size-zero objects then $PSET (A)$ has generating function $\prod_{n \geq 1} (1 + x^{n})^{a_{n}}$

Statement

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

$A (x) = \sum_{n \geq 1} a_{n} x^{n} .$

Then $PSET (A)$ is a combinatorial class and

$OGF (PSET (A)) = \prod_{n \geq 1} (1 + x^{n})^{a_{n}} .$

Facts & Assumptions

Given: A combinatorial class $A$ with no size-zero objects and counting sequence $(a_{n})_{n \geq 1}$ .

[L1]

Proof

technique · direct

1.1

For one fixed object $u \in A$ of size $n \geq 1$ , a powerset object either omits $u$ or includes it once, so the contribution of $u$ is the two-term series $1 + x^{n}$ .

construct

2.1

A powerset object is a simultaneous yes-or-no choice for every object of $A$ . Since every object has positive size, only finitely many such choices can affect a fixed degree, so the per-object factors of step 1.1 form a locally finite product that can be regrouped by [L1]. This also shows that each size layer of $PSET (A)$ is finite.

step 1.1L1

3.1

For each $n \geq 1$ there are exactly $a_{n}$ objects of size $n$ , and each contributes one factor $1 + x^{n}$ . Regrouping the locally finite product of step 2.1 therefore gives $OGF (PSET (A)) = \prod_{n \geq 1} (1 + x^{n})^{a_{n}}$ .

step 2.1L1∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Over a commutative $Q$ -algebra, $PSET (A)$ has generating function $\exp (\sum_{k \geq 1} (- 1)^{k - 1} A (x^{k}) / k)$

Statement

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

$A (x) = \sum_{n \geq 1} a_{n} x^{n} .$

Over a commutative $Q$ -algebra,

$OGF (PSET (A)) = \exp (\sum_{k \geq 1} \frac{(- 1)^{k - 1} A (x^{k})}{k}) .$

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[L1]

If $A$ has no size-zero objects then $OGF (PSET (A)) = \prod_{n \geq 1} (1 + x^{n})^{a_{n}}$ (If $A$ has no size-zero objects then $PSET (A)$ has generating function $\prod_{n \geq 1} (1 + x^{n})^{a_{n}}$ ).

[L2]

[L3]

The formal logarithm is $\log (1 + u) = \sum_{j \geq 1} (- 1)^{j - 1} u^{j} / j$ (Formal exponential, logarithm, and binomial powers over a commutative $Q$ -algebra).

Proof

technique · direct

1.1

Let $P (x)$ denote the powerset generating function. By [L1], $P (x) = \prod_{n \geq 1} (1 + x^{n})^{a_{n}}$ , so applying $\log$ and using [L2] gives $\log P (x) = \sum_{n \geq 1} a_{n} \log (1 + x^{n})$ .

L1L2

2.1

By [L3], $\log (1 + x^{n}) = \sum_{k \geq 1} (- 1)^{k - 1} x^{n k} / k$ , so $\log P (x) = \sum_{n \geq 1} \sum_{k \geq 1} (- 1)^{k - 1} a_{n} x^{n k} / k = \sum_{k \geq 1} ((- 1)^{k - 1} / k) \sum_{n \geq 1} a_{n} (x^{k})^{n} = \sum_{k \geq 1} (- 1)^{k - 1} A (x^{k}) / k$ . Again the rearrangement is coefficientwise finite in every degree.

step 1.1L3algebra

3.1

Exponentiating step 2.1 and using the inverse relation of [L2] gives the stated formula for $P (x)$ .

step 2.1L2∎

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

The cycle construction $CYC (A)$

Definition

Let $A$ be a combinatorial class. For each $m \geq 1$ , let $C_{m} = Z / m$ act on the set of $m$ -tuples

$A^{m} = {(a_{0}, \dots, a_{m - 1}) : a_{i} \in A}$

by cyclic rotation:

$[r]_{m} \cdot (a_{0}, \dots, a_{m - 1}) : = (a_{r}, a_{r + 1}, \dots, a_{m - 1}, a_{0}, \dots, a_{r - 1}) .$

The cycle construction $CYC (A)$ is the disjoint union, over all $m \geq 1$ , of the orbit sets of these actions. An object of $CYC (A)$ is therefore a cyclic arrangement of finitely many $A$ -objects, and its size is

$∣ (a_{0}, \dots, a_{m - 1}) ∣ : = ∣ a_{0} ∣ + \dots + ∣ a_{m - 1} ∣,$

which is constant on each orbit.

If $A$ has a size-zero object, then arbitrarily long cycles may have the same total size. The generating-function theorem for $CYC$ therefore assumes that $A$ has no size-zero objects.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

A tuple fixed by a cyclic rotation is determined by a shorter periodic block

Statement

Let $m \geq 1$ , let $0 \leq r < m$ , and put $d : = \gcd (m, r)$ . For an $m$ -tuple $u = (u_{0}, \dots, u_{m - 1})$ , the following are equivalent:

rotation by $r$ places fixes $u$ ;
whenever $i \equiv j (m o d d)$ , one has $u_{i} = u_{j}$ ;
there is a $d$ -tuple $(b_{0}, \dots, b_{d - 1})$ such that $u_{i} = b_{i m o d d}$ for every $i$ .

In particular a tuple fixed by rotation by $r$ places is determined by its first $d$ entries and is obtained by repeating that shorter block exactly $m / d$ times.

Facts & Assumptions

Given: Integers $m \geq 1$ and $0 \leq r < m$ , the integer $d : = \gcd (m, r)$ , and an $m$ -tuple $u = (u_{0}, \dots, u_{m - 1})$ .

[L1]

The congruence $r q \equiv t (m o d m)$ is solvable exactly when $\gcd (r, m) ∣ t$ (For $n \geq 1$ , $a x \equiv b (m o d n)$ is solvable exactly when $\gcd (a, n) ∣ b$ , and then has exactly $\gcd (a, n)$ solution classes modulo $n$ ).

Proof

technique · direct

1.1

Assume rotation by $r$ places fixes $u$ . Then one application of the rotation gives $u_{i} = u_{i + r m o d m}$ for every index $i$ , and iterating gives $u_{i} = u_{i + q r m o d m}$ for every $q \geq 0$ .

given

1.2

If condition 2 holds, define $b_{s} : = u_{s}$ for $0 \leq s < d$ . Every index $i$ has a unique residue class modulo $d$ , and condition 2 makes $u_{i}$ depend only on that class, so $u_{i} = b_{i m o d d}$ for every $i$ . This is condition 3.

givenconstruct

2.1

If $i \equiv j (m o d d)$ , then $d ∣ (j - i)$ . Since $\gcd (r, m) = d$ , [L1] gives an integer $q$ with $r q \equiv j - i (m o d m)$ , and step 1.1 therefore gives $u_{i} = u_{j}$ . This proves 1 implies 2.

step 1.1L1

2.2

If condition 3 holds, then $d ∣ r$ , so $(i + r) m o d d = i m o d d$ for every $i$ . Hence $u_{i + r m o d m} = b_{(i + r) m o d d} = b_{i m o d d} = u_{i}$ , so rotation by $r$ places fixes $u$ . Thus 3 implies 1.

step 1.2L1algebra

3.1

Steps 2.1, 1.2, and 2.2 prove the equivalence of the three conditions and the final periodic-block description.

step 2.1step 1.2step 2.2∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26Open item page →

Over a commutative $Q$ -algebra, $CYC (A)$ has generating function $\sum_{k \geq 1} \frac{φ (k)}{k} \log \frac{1}{1 - A (x^{k})}$

Statement

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

$A (x) = \sum_{n \geq 1} a_{n} x^{n} .$

Over a commutative $Q$ -algebra,

$OGF (CYC (A)) = \sum_{k \geq 1} \frac{φ (k)}{k} \log \frac{1}{1 - A (x^{k})} .$

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, $∣ G ∣ ∣ X / G ∣ = \sum_{g \in G} ∣ X^{g} ∣$ (Cauchy-Frobenius orbit counting: $∣ G ∣ ∣ X / G ∣ = \sum_{g \in G} ∣ X^{g} ∣$ 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 $k \geq 1$ , 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)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ , For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[L4]

The formal logarithm is $\log (1 + u) = \sum_{j \geq 1} (- 1)^{j - 1} u^{j} / j$ (Formal exponential, logarithm, and binomial powers over a commutative $Q$ -algebra).

Proof

technique · direct

1.1

For each $m \geq 1$ , let $C_{m}$ 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 $A^{m}$ is finite. Applying [L1] degree by degree to the cyclic action of $C_{m}$ therefore gives $OGF (C_{m}) = (1 / m) \sum_{r = 0}^{m - 1} F_{m, r} (x)$ , where $F_{m, r} (x)$ is the generating function of the $m$ -tuples fixed by rotation by $r$ places.

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 $F_{m, r} (x) = A (x^{k})^{d} = A (x^{m / d})^{d}$ .

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 = d s$ with $0 \leq s < k$ and $\gcd (s, k) = 1$ , so [L3] shows that there are $φ (k)$ of them. Step 1.2 therefore gives $OGF (C_{m}) = (1 / m) \sum_{k ∣ m} φ (k) A (x^{k})^{m / k}$ .

step 1.2L3algebra

3.1

Summing step 2.1 over all $m \geq 1$ and writing $m = d k$ yields $OGF (CYC (A)) = \sum_{k \geq 1} (φ (k) / k) \sum_{d \geq 1} A (x^{k})^{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 (x^{k})$ gives $\sum_{d \geq 1} A (x^{k})^{d} / d = \log (1 / (1 - A (x^{k})))$ . Substituting this into step 3.1 gives the stated cycle formula.

step 3.1L4∎

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

The number of necklaces of length $n$ on an $m$ -letter alphabet is $\frac{1}{n} \sum_{d ∣ n} φ (d) m^{n / d}$

Statement

Let $m \geq 1$ and $n \geq 1$ . The number of necklaces of length $n$ on an $m$ -letter alphabet is

$\frac{1}{n} \sum_{d ∣ n} φ (d) m^{n / d} .$

Facts & Assumptions

Given: Naturals $m \geq 1$ and $n \geq 1$ , and the class $A : = m Z$ of $m$ coloured atoms.

[L1]

If a combinatorial class $A$ has no size-zero objects, then over a commutative $Q$ -algebra its cycle construction has generating function $OGF (CYC (A)) = \sum_{k \geq 1} \frac{φ (k)}{k} \log \frac{1}{1 - A (x^{k})}$ (Over a commutative $Q$ -algebra, $CYC (A)$ has generating function $\sum_{k \geq 1} \frac{φ (k)}{k} \log \frac{1}{1 - A (x^{k})}$ ).

Proof

technique · direct

1.1

The class $A$ has generating function $A (x) = m x$ . Its cycle class is exactly the class of coloured necklaces, with size equal to necklace length.

construct

1.2

For each $k \geq 1$ , one has $\log (1 / (1 - m x^{k})) = \sum_{j \geq 1} m^{j} x^{k j} / j$ , so the coefficient of $x^{n}$ in this series is $0$ unless $k ∣ n$ , and is $m^{n / k} / (n / k)$ when $k ∣ n$ .

algebra

2.1

Taking the coefficient of $x^{n}$ in [L1] and using steps 1.1 and 1.2 gives $[x^{n}] OGF (CYC (A)) = \sum_{k ∣ n} (φ (k) / k) \cdot (m^{n / k} / (n / k)) = (1 / n) \sum_{k ∣ n} φ (k) m^{n / k}$ . This coefficient is exactly the number of necklaces of length $n$ .

step 1.1step 1.2L1algebra∎

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Substitution of combinatorial classes

Definition

Let $A$ and $B$ be combinatorial classes. Their substitution $A \circ B$ is the class of pairs

$(a, (b_{1}, \dots, b_{r}))$

such that $a \in A$ has size $r$ and each $b_{i} \in B$ . Its size is

$∣ (a, (b_{1}, \dots, b_{r})) ∣ : = ∣ b_{1} ∣ + \dots + ∣ b_{r} ∣ .$

The point is that an object of size $r$ in $A$ supplies exactly $r$ ordered slots to be filled by $B$ -objects.

If $B$ has a size-zero object, then for suitable outer classes $A$ fixed total size can arise from arbitrarily large values of $r$ , so the substituted class need not be combinatorial. The substitution theorem therefore assumes $[x^{0}] B (x) = 0$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

If $B (0) = 0$ then $A \circ B$ has generating function $A (B (x))$

Statement

Let $A$ and $B$ be combinatorial classes with ordinary generating functions

$A (x) = \sum_{r \geq 0} a_{r} x^{r}, B (x) = \sum_{n \geq 0} b_{n} x^{n},$

and suppose $B (0) = 0$ . Then $A \circ B$ is a combinatorial class and

$OGF (A \circ B) = A (B (x)) .$

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[L1]

Formal composition is $f \circ g = \sum_{r \geq 0} [x^{r}] f g^{r}$ , and it is admissible when $g (0) = 0$ (Composition $f \circ g$ of formal series when the outer series is a polynomial or the inner series has zero constant term).

[L2]

Substitution by a zero-constant series is a ring homomorphism (Substitution by a zero-constant series is a ring homomorphism, and composition is associative when both inner series have zero constant coefficient).

Proof

technique · direct

1.1

Fix $r \geq 0$ . An object of size $r$ in $A$ contributes one ordered list of $r$ slots, and filling those slots with $B$ -objects is counted by $B (x)^{r}$ . Since there are $a_{r}$ choices for the outer object, the total contribution of all outer objects of size $r$ is $a_{r} B (x)^{r}$ .

construct

2.1

Because $B (0) = 0$ , every $B$ -object has positive size. Therefore an object of total size $n$ in $A \circ B$ can only come from outer size $r \leq n$ , so each size layer is finite and the total generating function is $\sum_{r \geq 0} a_{r} B (x)^{r}$ .

step 1.1given

3.1

The series of step 2.1 is exactly the admissible formal composition $A (B (x))$ by [L1], and [L2] records that substitution by a zero-constant series is the corresponding ring operation on formal series. Hence $OGF (A \circ B) = A (B (x))$ .

step 2.1L1L2∎

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Pointing a combinatorial class

Definition

Let $A$ be a combinatorial class. Its pointing $Θ A$ is the class of pairs

$Θ A : = {(a, p) : a \in A, 1 \leq p \leq ∣ a ∣},$

with size $∣ (a, p) ∣ : = ∣ a ∣$ .

Thus a pointed object is an $A$ -object together with a distinguished atomic position. Objects of size $0$ contribute nothing to $Θ A$ , because there is no index $p$ with $1 \leq p \leq 0$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26Open item page →

Pointing translates to $x A^{'} (x)$

Statement

Let $A$ be a combinatorial class with ordinary generating function

$A (x) = \sum_{n \geq 0} a_{n} x^{n} .$

Then

$OGF (Θ A) = x A^{'} (x) .$

Facts & Assumptions

Given: A combinatorial class $A$ with counting sequence $(a_{n})$ and ordinary generating function $A (x)$ .

[L1]

The formal derivative of $\sum_{n \geq 0} a_{n} x^{n}$ is $\sum_{n \geq 1} n a_{n} x^{n - 1}$ (The formal derivative $D (\sum a_{n} x^{n}) = \sum_{n \geq 1} n a_{n} x^{n - 1}$ ).

Proof

technique · direct

1.1

For each $n \geq 0$ , every size- $n$ object of $A$ contributes exactly $n$ pointed objects of size $n$ , one for each distinguished position. Hence the size- $n$ layer of $Θ A$ has cardinality $n a_{n}$ .

given

2.1

Therefore $OGF (Θ A) = \sum_{n \geq 0} n a_{n} x^{n} = x \sum_{n \geq 1} n a_{n} x^{n - 1} = x A^{'} (x)$ , using [L1] for the last equality.

step 1.1L1algebra∎

DefinitionDefinition: AI-adaptedProof: Not applicableaudited 2026-08-26Open item page →

Combinatorial specifications and order-raising recursive specifications

Definition

Fix a commutative ring $R$ .

A combinatorial specification for an unknown class $Y$ is an equation

$Y = Φ (Y)$

whose right-hand side is built from already defined classes and from $Y$ using symbolic constructions whose generating-function operations are defined over $R$ . Replacing those constructions by their generating-function operations produces an associated operation $F_{Φ} (f)$ whenever all the required formal-series operations are defined at $f$ . Write

$D_{Φ} : = {f \in R ⟦ x ⟧ : F_{Φ} (f) is defined}$

for its natural domain. For example, a factor $SEQ (Y)$ contributes $(1 - f)^{- 1}$ , which is defined precisely when the constant coefficient of $1 - f$ is a unit; being defined over $R$ does not make this operation total on $R ⟦ x ⟧$ .

Thus a specification using a construction whose series formula needs rational scalars, such as $CYC$ , is admitted here only when $R$ is a commutative $Q$ -algebra and the input satisfies that construction's order and constant-term conditions.

A nonempty set $D \subseteq D_{Φ}$ is an admissible domain when $F_{Φ} (D) \subseteq D$ . The specification is order-raising on $D$ when

${ord}_{x} (F_{Φ} (f) - F_{Φ} (g)) \geq {ord}_{x} (f - g) + 1$

for all $f, g \in D$ . When $D = R ⟦ x ⟧$ , so that $F_{Φ}$ is a total endomorphism of the whole series ring, we call the specification simply an order-raising recursive specification and write

$F_{Φ} : R ⟦ x ⟧ ⟶ R ⟦ x ⟧ .$

This is the $x$ -adic contraction condition. It says that changing the input only changes the output in strictly higher order, so successive coefficient prefixes stabilize. Specifications on a proper admissible domain require the corresponding invariant-domain fixed-point theorem; the total-map theorem developed here applies to the unqualified notion.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-26Open item page →

An order-raising recursive specification has a unique solution

Statement

Let $R$ be a commutative ring, and let

$F : R ⟦ x ⟧ \to R ⟦ x ⟧$

satisfy

${ord}_{x} (F (f) - F (g)) \geq {ord}_{x} (f - g) + 1$

for all formal series $f, g$ . Then there is a unique formal series $y$ with $F (y) = y$ .

Equivalently, once a commutative coefficient ring is fixed, every order-raising recursive specification has a unique generating-function solution.

Facts & Assumptions

Given: A commutative ring $R$ and an operator $F : R ⟦ x ⟧ \to R ⟦ x ⟧$ satisfying the displayed order-raising inequality.

[L1]

Formal order is non-Archimedean under sums: in particular, ${ord}_{x} (f + g) \geq \min ({ord}_{x} f, {ord}_{x} g)$ (Formal order is non-Archimedean under sums and additive under products over a domain).

[L2]

Every $x$ -adically Cauchy sequence in $R ⟦ x ⟧$ has a unique $x$ -adic limit ( $R ⟦ x ⟧$ is complete in the $x$ -adic topology and $R [x]$ is dense by truncation).

Proof

technique · direct

1.1

Define a sequence by $f_{0} : = 0$ and $f_{j + 1} : = F (f_{j})$ . Then ${ord}_{x} (f_{j + 1} - f_{j}) \geq j$ for every $j$ : the case $j = 0$ is automatic, and if it holds at $j$ then ${ord}_{x} (f_{j + 2} - f_{j + 1}) = {ord}_{x} (F (f_{j + 1}) - F (f_{j})) \geq {ord}_{x} (f_{j + 1} - f_{j}) + 1 \geq j + 1$ .

given

2.1

For $p > q$ , write $f_{p} - f_{q} = (f_{p} - f_{p - 1}) + \dots + (f_{q + 1} - f_{q})$ . Step 1.1 and [L1] give ${ord}_{x} (f_{p} - f_{q}) \geq q$ , so $(f_{j})$ is $x$ -adically Cauchy.

step 1.1L1

3.1

By [L2], the sequence $(f_{j})$ has a unique $x$ -adic limit; call it $y$ .

step 2.1L2choose

4.1

The order-raising hypothesis applied to $f_{j}$ and $y$ gives ${ord}_{x} (F (f_{j}) - F (y)) \geq {ord}_{x} (f_{j} - y) + 1$ , so $F (f_{j}) \to F (y)$ in the $x$ -adic topology. But $F (f_{j}) = f_{j + 1}$ , and $f_{j + 1} \to y$ as well, hence $F (y) = y$ .

step 3.1given

5.1

If $z$ is another fixed point and $z \neq y$ , put $p : = {ord}_{x} (y - z)$ . Then $p = {ord}_{x} (F (y) - F (z)) \geq p + 1$ , impossible. Hence $z = y$ .

step 4.1givenassume-contradischarge-contradiction

6.1

Step 4.1 gives existence of a fixed point and step 5.1 gives uniqueness, so the recursive specification has exactly one solution.

step 4.1step 5.1∎

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26Open item page →

Rooted plane trees satisfy $T (x) = x / (1 - T (x))$

Statement

Let $T (x)$ be the generating function of rooted plane trees, specified by

$T = Z \times SEQ (T) .$

Then $T (x)$ is the unique formal power series with zero constant coefficient satisfying

$T (x) = \frac{x}{1 - T (x)} .$

Facts & Assumptions

Given: The recursive specification $T = Z \times SEQ (T)$ .

[L1]

If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$ (If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$ ).

[L2]

Every $x$ -adically Cauchy sequence in $Z ⟦ x ⟧$ has a unique $x$ -adic limit ( $R ⟦ x ⟧$ is complete in the $x$ -adic topology and $R [x]$ is dense by truncation).

[L3]

Formal order is additive under multiplication by $x$ , and a unit has order $0$ (Formal order is non-Archimedean under sums and additive under products over a domain, A formal power series is a unit exactly when its constant coefficient is a unit).

[L4]

The atomic class $Z$ has generating function $x$ , and every object of $Z$ has size $1$ (The neutral class $E$ and the atomic class $Z$ ).

Proof

technique · direct

1.1

On the set $x Z ⟦ x ⟧$ of series with zero constant coefficient, define $F (Y) = x / (1 - Y)$ . This is well defined because $1 - Y$ has constant coefficient $1$ . For $U, V$ in this set, $F (U) - F (V) = x (U - V) / ((1 - U) (1 - V))$ ; both denominators are units of order $0$ , so [L3] gives ${ord}_{x} (F (U) - F (V)) \geq {ord}_{x} (U - V) + 1$ . Moreover $F (Y)$ again has zero constant coefficient.

L3algebra

1.2

Every object of $T$ has a root from the atomic class $Z$ , so every tree has size at least $1$ . Thus $T$ has no size-zero objects.

givenL4

2.1

Define $T_{0} : = 0$ and $T_{j + 1} : = F (T_{j})$ . Step 1.1 gives ${ord}_{x} (T_{j + 1} - T_{j}) \geq j$ by induction on $j$ , and [L3] then shows that $(T_{j})$ is $x$ -adically Cauchy. By [L2] it has an $x$ -adic limit $T$ , whose constant coefficient is $0$ .

step 1.1L2L3choose

3.1

Step 1.1 also gives $F (T_{j}) \to F (T)$ . Since $F (T_{j}) = T_{j + 1}$ and the shifted sequence has the same limit $T$ , uniqueness of limits from [L2] yields $F (T) = T$ .

step 1.1step 2.1L2

4.1

If $U, V \in x Z ⟦ x ⟧$ are distinct fixed points and $p : = {ord}_{x} (U - V)$ , then step 1.1 gives $p = {ord}_{x} (F (U) - F (V)) \geq p + 1$ , a contradiction. Thus $T$ is the unique zero-constant fixed point.

step 1.1step 3.1assume-contradischarge-contradiction

5.1

Applying [L1] to $SEQ (T)$ and using [L4] for the root factor shows that $SEQ (T)$ has generating function $1 / (1 - T (x))$ , while $Z$ contributes $x$ . Therefore the defining equation of $T$ reads $T (x) = x / (1 - T (x))$ , and step 4.1 gives the asserted uniqueness in the zero-constant class.

step 1.2step 4.1L1L4∎

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26Open item page →

Rooted plane binary trees satisfy $B (x) = 1 + x B (x)^{2}$

Statement

Let $B (x)$ be the generating function of rooted plane binary trees, specified by

$B = E + Z \times B^{2} .$

Then $B (x)$ is the unique formal power series satisfying

$B (x) = 1 + x B (x)^{2} .$

Facts & Assumptions

Given: The recursive specification $B = E + Z \times B^{2}$ .

[L1]

[L2]

An order-raising recursive specification has a unique solution (An order-raising recursive specification has a unique solution).

[L3]

Formal order is non-Archimedean under sums and satisfies ${ord}_{x} (f g) \geq {ord}_{x} (f) + {ord}_{x} (g)$ over a commutative ring (Formal order is non-Archimedean under sums and additive under products over a domain).

Proof

technique · direct

1.1

The associated operator is $F (Y) = 1 + x Y^{2}$ . For any $U, V$ , one has $F (U) - F (V) = x (U + V) (U - V)$ , so [L3] gives ${ord}_{x} (F (U) - F (V)) \geq {ord}_{x} (U - V) + 1$ . Thus the specification is order-raising.

L3algebra

2.1

By [L2], the specification has a unique formal power series solution $B (x)$ .

step 1.1L2

3.1

The neutral class contributes $1$ , the atomic class contributes $x$ , and the ordered pair of left and right subtrees contributes $B (x)^{2}$ by [L1]. Hence the specification translates to $B (x) = 1 + x B (x)^{2}$ .

step 2.1L1∎

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Binary words of length at most three from $SEQ (2 Z)$

Example

The class $SEQ (2 Z)$ gives binary words. Up to length $3$ the words are

$ϵ,$

$0, 1,$

$00, 01, 10, 11,$

$000, 001, 010, 011, 100, 101, 110, 111.$

So the initial coefficient sequence is $1, 2, 4, 8$ .

Facts & Assumptions

Given: The binary-word generating function $OGF (B) = 1 / (1 - 2 x)$ (Binary words have generating function $1 / (1 - 2 x)$ ).

Verification

technique · direct

1.1

The displayed list has $1$ word of length $0$ , $2$ of length $1$ , $4$ of length $2$ , and $8$ of length $3$ .

given

2.1

Expanding $1 / (1 - 2 x)$ as $1 + 2 x + 4 x^{2} + 8 x^{3} + \dots$ gives the same initial coefficients, so the explicit list matches the theorem.

step 1.1∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

The compositions of $4$ from ${SEQ}_{\geq 1} ({SEQ}_{\geq 1} (Z))$

Example

The eight compositions of $4$ are

$4,$

$3 + 1, 1 + 3, 2 + 2,$

$2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2,$

$1 + 1 + 1 + 1.$

They split by number of parts as $1, 3, 3, 1$ .

Facts & Assumptions

Given: Compositions are nonempty sequences of positive integers (Positive-integer compositions have generating function $x / (1 - 2 x)$ ).

[L1]

The number of compositions of $n$ into exactly $k$ positive parts is $(\binom{n - 1}{k - 1})$ (Compositions of $n$ into $k$ positive parts are counted by $(\binom{n - 1}{k - 1})$ ).

Verification

technique · direct

1.1

The displayed list contains every ordered positive-part sum of $4$ : one with $1$ part, three with $2$ parts, three with $3$ parts, and one with $4$ parts.

given

2.1

The part-counts match [L1]: $(\binom{3}{0}) = 1$ , $(\binom{3}{1}) = 3$ , $(\binom{3}{2}) = 3$ , and $(\binom{3}{3}) = 1$ .

step 1.1L1algebra∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Partitions with parts at most $3$ from a truncated multiset product

Example

Restricting the Euler product to part sizes $1, 2, 3$ gives

$\frac{1}{(1 - x) (1 - x^{2}) (1 - x^{3})} .$

The coefficient of $x^{5}$ is $5$ , corresponding to the five partitions of $5$ whose parts are at most $3$ :

$3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1.$

Facts & Assumptions

Given: A combinatorial class having one object of each size $1$ , $2$ , and $3$ , and no other objects.

[L1]

If $A$ has no size-zero objects and $a_{n}$ objects of size $n$ , then $MSET (A)$ has generating function $\prod_{n \geq 1} (1 - x^{n})^{- a_{n}}$ (If $A$ has no size-zero objects then $MSET (A)$ has generating function $\prod_{n \geq 1} (1 - x^{n})^{- a_{n}}$ ).

Verification

technique · direct

1.1

Applying [L1] to the Given class and multiplying the resulting factors to degree $5$ gives $(1 - x)^{- 1} (1 - x^{2})^{- 1} (1 - x^{3})^{- 1} = (1 + x + x^{2} + x^{3} + x^{4} + x^{5}) (1 + x^{2} + x^{4}) (1 + x^{3}) = 1 + x + 2 x^{2} + 3 x^{3} + 4 x^{4} + 5 x^{5} + O (x^{6})$ .

givenL1algebra

2.1

The five displayed partitions of $5$ are exactly the partitions whose part sizes lie in ${1, 2, 3}$ , so the coefficient $5$ has the advertised interpretation.

step 1.1∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Plane trees with at most four vertices from $T = Z \times SEQ (T)$

Example

The rooted plane trees on at most four vertices are counted by the first coefficients of the Catalan series:

$1, 1, 2, 5.$

Concretely there is one tree on one vertex, one on two vertices, two on three vertices, and five on four vertices.

Facts & Assumptions

Given: The plane-tree generating function satisfies $T (x) = x / (1 - T (x))$ (Rooted plane trees satisfy $T (x) = x / (1 - T (x))$ ).

Verification

technique · direct

1.1

Solving $T = x / (1 - T)$ coefficientwise gives $T (x) = x + x^{2} + 2 x^{3} + 5 x^{4} + \dots$ , so the first four counts are $1, 1, 2, 5$ .

givenalgebra

2.1

These are realized by the evident shapes: a single root; a root with one child; for three vertices, the chain and the root with two children; for four vertices, the chain of length four, the root with three children, the root with one child whose child has two children, and the two left-right orderings of a root with two children one of which has one child.

step 1.1∎

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Binary necklaces of length $6$ from both $CYC (2 Z)$ and Burnside's lemma

Example

There are $14$ binary necklaces of length $6$ .

Facts & Assumptions

Given: The necklace count $\frac{1}{n} \sum_{d ∣ n} φ (d) m^{n / d}$ (The number of necklaces of length $n$ on an $m$ -letter alphabet is $\frac{1}{n} \sum_{d ∣ n} φ (d) m^{n / d}$ ).

[L1]

Burnside's lemma counts orbits by averaging fixed points (Cauchy-Frobenius orbit counting: $∣ G ∣ ∣ X / G ∣ = \sum_{g \in G} ∣ X^{g} ∣$ for a finite group action).

Verification

technique · direct

1.1

The corollary with $m = 2$ and $n = 6$ gives $(1 / 6) (φ (1) 2^{6} + φ (2) 2^{3} + φ (3) 2^{2} + φ (6) 2^{1}) = (1 / 6) (64 + 8 + 8 + 4) = 14$ .

givenalgebra

1.2

Burnside gives the same value. The six rotations of a $6$ -bead necklace fix $64, 2, 4, 8, 4, 2$ colourings respectively, since the numbers of position-orbits are $6, 1, 2, 3, 2, 1$ . Their average is $(64 + 2 + 4 + 8 + 4 + 2) / 6 = 14$ .

L1algebra

2.1

The cycle-construction count and the direct Burnside count therefore agree at length $6$ .

step 1.1step 1.2∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-08-26Open item page →

Iterating a recursive specification to determine coefficients through degree $6$

Example

For the plane-tree equation

$T = \frac{x}{1 - T},$

start with $T_{0} : = 0$ and define $T_{j + 1} : = x / (1 - T_{j})$ , truncating modulo $x^{7}$ . The iterates are

$T_{1} = x,$

$T_{2} = x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6},$

$T_{3} = x + x^{2} + 2 x^{3} + 4 x^{4} + 8 x^{5} + 16 x^{6},$

$T_{4} = x + x^{2} + 2 x^{3} + 5 x^{4} + 13 x^{5} + 34 x^{6},$

$T_{5} = x + x^{2} + 2 x^{3} + 5 x^{4} + 14 x^{5} + 41 x^{6},$

$T_{6} = x + x^{2} + 2 x^{3} + 5 x^{4} + 14 x^{5} + 42 x^{6} .$

So the coefficients through degree $6$ are $1, 1, 2, 5, 14, 42$ .

Facts & Assumptions

Given: The plane-tree series is the unique fixed point of $Y \mapsto x / (1 - Y)$ (Rooted plane trees satisfy $T (x) = x / (1 - T (x))$ ), and order-raising recursion converges coefficientwise by successive truncation (An order-raising recursive specification has a unique solution).

Verification

technique · direct

1.1

Substituting each displayed iterate into $x / (1 - Y)$ and truncating modulo $x^{7}$ gives the next one in the list.

givenalgebra

2.1

By the sixth iterate, every coefficient through degree $6$ has stabilized, so the unique fixed point begins $T (x) = x + x^{2} + 2 x^{3} + 5 x^{4} + 14 x^{5} + 42 x^{6} + \dots$ .

step 1.1given∎

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

A family with infinitely many objects of size $2$ is not a combinatorial class

Counterexample

Let $A : = {a_{0}, a_{1}, a_{2}, \dots}$ and define $∣ a_{j} ∣ : = 2$ for every $j \in N$ . Then the level $A_{2}$ is infinite, so $A$ is not a combinatorial class.

Facts & Assumptions

Given: A combinatorial class is required to have finite size- $n$ levels for every $n$ (Combinatorial classes, counting sequences and ordinary generating functions).

Verification

technique · direct

1.1

The size- $2$ level of the displayed family is $A_{2} = {a_{0}, a_{1}, a_{2}, \dots}$ , which is infinite.

given

2.1

This violates the defining finiteness condition on levels, so the family is not a combinatorial class.

step 1.1given∎

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

Without disjoint copies, union does not add generating functions

Counterexample

Let $A = B = {a}$ with $∣ a ∣ = 1$ , and form the ordinary set-theoretic union $A \cup B = {a}$ without adding tags. Then

$OGF (A) = x, OGF (B) = x, OGF (A \cup B) = x \neq 2 x .$

Facts & Assumptions

Given: The symbolic sum rule is proved only for the tagged disjoint union $A + B$ (Disjoint union and Cartesian product translate to addition and multiplication of ordinary generating functions, Disjoint unions and Cartesian products of combinatorial classes).

Verification

technique · direct

1.1

The ordinary union $A \cup B$ has one object of size $1$ , so its generating function is $x$ .

given

2.1

The sum $OGF (A) + OGF (B)$ is $x + x = 2 x$ , which is different from step 1.1. The failure is exactly the missing disjointness: the same object was counted twice on the right and once on the left.

step 1.1givenalgebra∎

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

A product class without unique factorisation does not have generating function $A (x) B (x)$

Counterexample

Let $A = {a}$ with $∣ a ∣ = 1$ , let $B = {b_{0}, b_{1}}$ with $∣ b_{0} ∣ = ∣ b_{1} ∣ = 1$ , and let $C = {c}$ with $∣ c ∣ = 2$ . Suppose a would-be product construction sends both pairs $(a, b_{0})$ and $(a, b_{1})$ to the same object $c$ . Then

$OGF (A) = x, OGF (B) = 2 x, OGF (C) = x^{2} \neq 2 x^{2} .$

Facts & Assumptions

Given: The symbolic product rule applies to the Cartesian product, where the ordered pair itself records both components (Disjoint union and Cartesian product translate to addition and multiplication of ordinary generating functions, Disjoint unions and Cartesian products of combinatorial classes).

Verification

technique · direct

1.1

The class $A \times B$ has two size- $2$ objects, namely $(a, b_{0})$ and $(a, b_{1})$ , so its generating function is $2 x^{2}$ .

given

2.1

The collapsed construction $C$ has only one size- $2$ object, so its generating function is $x^{2}$ . The missing factor of $2$ is exactly the loss of unique factorisation.

step 1.1given∎

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

FALSE: $SEQ (A)$ is a combinatorial class even when $A$ has a size-zero object

Statement

False claim: $SEQ (A)$ is always a combinatorial class, even when $A$ has an object of size $0$ .

The theorem If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$ excludes exactly this case, and the exclusion is necessary.

Facts & Assumptions

Given: The sequence construction (The sequence construction $SEQ (A)$ ) and its generating function theorem, which assumes that $A$ has no size-zero objects (If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$ ).

Refutation

technique · direct

1.1

Let $A = {e}$ with $∣ e ∣ = 0$ . Then for every $r \geq 0$ , the length- $r$ sequence $(e, \dots, e)$ lies in $SEQ (A)$ and has total size $0$ .

given

2.1

These sequences are all distinct because their lengths differ, so the size- $0$ level of $SEQ (A)$ is infinite. Hence $SEQ (A)$ is not a combinatorial class.

step 1.1given

3.1

The claim is therefore false, and the no-size-zero hypothesis in the sequence theorem is load bearing.

step 2.1given∎

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-26Open item page →

FALSE: the positive-size multiset product always encodes a valid multiset class

Statement

False claim: once one knows the positive-size counts $(a_{n})_{n \geq 1}$ , the formal product

$\prod_{n \geq 1} (1 - x^{n})^{- a_{n}}$

automatically is the ordinary generating function of the multiset construction, with no further local-finiteness hypothesis on the underlying class.

The formal product itself is coefficientwise well defined. What is false is its unconditional interpretation as a multiset generating function: omitted size- $0$ behaviour can destroy local finiteness completely while leaving the displayed positive-size sequence unchanged.

Facts & Assumptions

Given: The multiset product theorem assumes that the underlying class has no size-zero objects (If $A$ has no size-zero objects then $MSET (A)$ has generating function $\prod_{n \geq 1} (1 - x^{n})^{- a_{n}}$ ).

[L1]

Well-defined locally finite products are the ones licensed by the summability machinery (Summable formal families may be regrouped and rearranged, distribute over multiplication, and have well-defined locally finite products).

Refutation

technique · direct

1.1

Let $A$ have one object $z$ of size $0$ and one object $u$ of size $1$ . Its positive-size counting sequence is $a_{1} = 1$ and $a_{n} = 0$ for $n > 1$ , so the displayed product is $(1 - x)^{- 1}$ .

given

2.1

But $MSET (A)$ has infinitely many size- $0$ objects: the multiplicity functions with $m (z) = 0, 1, 2, \dots$ and $m (u) = 0$ are all distinct and all have total size $0$ . So the would-be multiset class is not locally finite in degree $0$ , and [L1] does not license a generating function for it.

step 1.1L1given

3.1

The displayed product therefore does not automatically encode a valid multiset construction from the bare positive-size sequence alone. The omitted no-size-zero hypothesis matters, so the claim is false.

step 2.1given∎

Combinatorial Classes and the Symbolic Method

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Combinatorial classes, counting sequences and ordinary generating functions

Definition

The neutral class EE and the atomic class ZZ

Definition

Disjoint unions and Cartesian products of combinatorial classes

Definition

Disjoint union and Cartesian product translate to addition and multiplication of ordinary generating functions

Statement

Facts & Assumptions

Proof

The sequence construction SEQ⁡(A)SEQ(A)

Definition

If AA has no size-zero objects then SEQ⁡(A)SEQ(A) has generating function 1/(1−A(x))1/(1−A(x))

Statement

Facts & Assumptions

Proof

Binary words have generating function 1/(1−2x)1/(1−2x)

Statement

Facts & Assumptions

Proof

Positive-integer compositions have generating function x/(1−2x)x/(1−2x)

Statement

Facts & Assumptions

Proof

Compositions of nn into kk positive parts are counted by (n−1k−1)(k−1n−1​)

Statement

Facts & Assumptions

Proof

The multiset construction MSET⁡(A)MSET(A) and the powerset construction PSET⁡(A)PSET(A)

Definition

If AA has no size-zero objects then MSET⁡(A)MSET(A) has generating function ∏n≥1(1−xn)−an∏n≥1​(1−xn)−an​

Statement

Facts & Assumptions

Proof

Over a commutative QQ-algebra, MSET⁡(A)MSET(A) has generating function exp⁡(∑k≥1A(xk)/k)exp(∑k≥1​A(xk)/k)

Statement

Facts & Assumptions

Proof

Integer partitions have generating function ∏n≥1(1−xn)−1∏n≥1​(1−xn)−1

Statement

Facts & Assumptions

Proof

If AA has no size-zero objects then PSET⁡(A)PSET(A) has generating function ∏n≥1(1+xn)an∏n≥1​(1+xn)an​

Statement

Facts & Assumptions

Proof

Over a commutative QQ-algebra, PSET⁡(A)PSET(A) has generating function exp⁡(∑k≥1(−1)k−1A(xk)/k)exp(∑k≥1​(−1)k−1A(xk)/k)

Statement

Facts & Assumptions

Proof

The cycle construction CYC⁡(A)CYC(A)

Definition

A tuple fixed by a cyclic rotation is determined by a shorter periodic block

Statement

Facts & Assumptions

Proof

Over a commutative QQ-algebra, CYC⁡(A)CYC(A) has generating function ∑k≥1φ(k)klog⁡11−A(xk)∑k≥1​kφ(k)​log1−A(xk)1​

Statement

Facts & Assumptions

Proof

The number of necklaces of length nn on an mm-letter alphabet is 1n∑d∣nφ(d)mn/dn1​∑d∣n​φ(d)mn/d

Statement

Facts & Assumptions

Proof

Substitution of combinatorial classes

Definition

If B(0)=0B(0)=0 then A∘BA∘B has generating function A(B(x))A(B(x))

Statement

Facts & Assumptions

Proof

Pointing a combinatorial class

Definition

Pointing translates to xA′(x)xA′(x)

Statement

Facts & Assumptions

The neutral class $E$ and the atomic class $Z$

The sequence construction $SEQ (A)$

If $A$ has no size-zero objects then $SEQ (A)$ has generating function $1 / (1 - A (x))$

Binary words have generating function $1 / (1 - 2 x)$

Positive-integer compositions have generating function $x / (1 - 2 x)$

Compositions of $n$ into $k$ positive parts are counted by $(\binom{n - 1}{k - 1})$

The multiset construction $MSET (A)$ and the powerset construction $PSET (A)$

If $A$ has no size-zero objects then $MSET (A)$ has generating function $\prod_{n \geq 1} (1 - x^{n})^{- a_{n}}$

Over a commutative $Q$ -algebra, $MSET (A)$ has generating function $\exp (\sum_{k \geq 1} A (x^{k}) / k)$

Integer partitions have generating function $\prod_{n \geq 1} (1 - x^{n})^{- 1}$

If $A$ has no size-zero objects then $PSET (A)$ has generating function $\prod_{n \geq 1} (1 + x^{n})^{a_{n}}$

Over a commutative $Q$ -algebra, $PSET (A)$ has generating function $\exp (\sum_{k \geq 1} (- 1)^{k - 1} A (x^{k}) / k)$

The cycle construction $CYC (A)$

Over a commutative $Q$ -algebra, $CYC (A)$ has generating function $\sum_{k \geq 1} \frac{φ (k)}{k} \log \frac{1}{1 - A (x^{k})}$

The number of necklaces of length $n$ on an $m$ -letter alphabet is $\frac{1}{n} \sum_{d ∣ n} φ (d) m^{n / d}$

If $B (0) = 0$ then $A \circ B$ has generating function $A (B (x))$

Pointing translates to $x A^{'} (x)$

Rooted plane trees satisfy $T (x) = x / (1 - T (x))$

Rooted plane binary trees satisfy $B (x) = 1 + x B (x)^{2}$

Binary words of length at most three from $SEQ (2 Z)$

The compositions of $4$ from ${SEQ}_{\geq 1} ({SEQ}_{\geq 1} (Z))$

Partitions with parts at most $3$ from a truncated multiset product

Plane trees with at most four vertices from $T = Z \times SEQ (T)$

Binary necklaces of length $6$ from both $CYC (2 Z)$ and Burnside's lemma

Iterating a recursive specification to determine coefficients through degree $6$

A family with infinitely many objects of size $2$ is not a combinatorial class

A product class without unique factorisation does not have generating function $A (x) B (x)$

FALSE: $SEQ (A)$ is a combinatorial class even when $A$ has a size-zero object