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.
Combinatorial classes, counting sequences and ordinary generating functions
Definition
A combinatorial class is a pair consisting of a set and a size map such that, for every , the level
is finite (The cardinality of a finite set).
The counting sequence of is
Viewing each natural coefficient as its canonical integer by The naturals embed in the integers, its ordinary generating function is the formal power series
in the sense of Formal power series over a commutative ring and the coefficient-extraction functional .
An isomorphism of combinatorial classes is a bijection such that for every . Such a bijection identifies each level with the corresponding level , so isomorphic classes have the same counting sequence and the same ordinary generating function.
Depends on
Used by
- Integer partitions have generating function ∏_n≥ 1(1-xⁿ)⁻¹ Corollary
- A family with infinitely many objects of size 2 is not a combinatorial class Counterexample
- Combinatorial specifications and order-raising recursive specifications Definition
- Disjoint unions and Cartesian products of combinatorial classes Definition
- Pointing a combinatorial class Definition
- Substitution of combinatorial classes Definition
- The cycle construction CYC(A) Definition
- The multiset construction MSET(A) and the powerset construction PSET(A) Definition
- The neutral class E and the atomic class Z Definition
- The sequence construction SEQ(A) Definition
Dependency tree · two levels
19 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)