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.
The labelled constructions translate into the usual exponential-generating-function rules
Statement
Let and be labelled classes with exponential generating functions and over a commutative -algebra. Then:
If , then
For the boxed product,
and the constant term is , so
Facts & Assumptions
Given: The labelled constructions of Labelled classes, labelled product, and the constructions , , , and boxed product and the formal identities in Formal and are inverse homomorphisms and formal binomial powers obey the expected addition laws.
Proof
In the labelled product on an -label set, choosing the labels sent to the -part contributes possibilities, and then one chooses an -object on those labels and a -object on the complement. Thus the size- coefficient is , which is exactly the coefficient rule for the product of exponential generating functions.
For , a sequence of length is an -fold labelled product of with itself, so its EGF is . Summing over all gives , and because this formal geometric series equals .
A labelled set of exactly -objects is the same data as an ordered -tuple of pairwise disjoint -objects modulo permutation of the components. Therefore its EGF is , and summing over gives by Formal and are inverse homomorphisms and formal binomial powers obey the expected addition laws.
A labelled cycle of exactly -objects has linear representatives, so its EGF is . Summing over gives by Formal and are inverse homomorphisms and formal binomial powers obey the expected addition laws.
In a boxed product, the smallest label lies in the -part. On size- labels this is equivalent to choosing a pointed -object on some labels, with the distinguished label forced to be the smallest, and then a -object on the remaining labels. Pointing contributes the derivative , so the derivative of the boxed-product EGF is . Since no boxed product has size , the constant term is , and integrating from to gives the displayed formula.
Steps 1.1-3.1 are exactly the labelled symbolic-method rules claimed in the statement.
Depends on
- Exponential generating functions over a commutative $\mathbb{Q}$-algebra
- Labelled classes, labelled product, and the constructions $\operatorname{SEQ}$, $\operatorname{SET}$, $\operatorname{CYC}$, and boxed product
- Substitution by a zero-constant series is a ring homomorphism, and composition is associative when both inner series have zero constant coefficient
- Formal $\exp$ and $\log$ are inverse homomorphisms and formal binomial powers obey the expected addition laws
- Summable formal families may be regrouped and rearranged, distribute over multiplication, and have well-defined locally finite products
Used by
- Standard labelled specializations give involutions, ordered Bell numbers, and partitions without singletons Corollary
- Set partitions whose blocks are all singletons have EGF eˣ Example
- FALSE: exponential generating functions multiply without the labelled-product hypothesis False statement
- The exponential formula gives the Bell-number generating function Theorem
- The two Stirling triangles have the expected vertical exponential generating functions Theorem
Dependency tree · two levels
15 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 — Symbolic Combinatorics (standard reference, not scraped)
- Herbert S. Wilf, generatingfunctionology, 2nd ed., §2.3 and ch. 3 (standard reference, not scraped)