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 Catalan generating function in
Definition
is a field (The rationals form a field) and therefore a commutative ring (Every field is a commutative ring with ; it is an integral domain, and it is a commutative division ring), so the formal power series and the coefficient functionals of Formal power series over a commutative ring and the coefficient-extraction functional are available over it.
Natural numbers as coefficients. A natural number written where a rational is expected denotes its image under the composite of the embedding , , of The naturals embed in the integers with the embedding of The integers embed in the rationals; no symbol is written for it. Both embeddings are injective and preserve addition and multiplication, so the composite does too, and by induction (The principle of mathematical induction) it therefore carries a finite sum or product of natural numbers to the corresponding finite sum or product of rationals. An identity between natural numbers may therefore be read as an identity between rationals, and conversely, the embedding being injective.
Definition. The Catalan generating function is the formal power series whose coefficient function is (The Catalan number ), that is
Two formal power series are equal exactly when all their coefficients agree (Coefficient extraction is -linear, separates formal series, shifts under multiplication by , and converts products to finite convolution), so is determined by this prescription and nothing else is asserted: the symbol is an indeterminate, no value is substituted for it, and no convergence is claimed.
as a commutative -algebra. The coefficientwise sum and the Cauchy product make a commutative ring, and the map sending a rational to the constant series with that coefficient at is an injective unital ring homomorphism (Cauchy multiplication makes a commutative ring containing as the finitely supported subring, applied to the polynomials of degree at most ). So is a commutative -algebra in the sense of Formal exponential, logarithm, and binomial powers over a commutative -algebra, and the formal exponential, logarithm and binomial powers of that item are available in it.
Remarks
-
Why and not . Every coefficient of is a natural number, so has a copy in . The square-root and binomial-power machinery used below is stated for a commutative -algebra, because its definitions divide by , and is not one. Working over from the start avoids moving between two rings in the middle of a computation.
-
A count read as a coefficient. The coefficients are the counts , and the reading of a natural number as a rational is the embedding recorded above. Nothing else changes: an identity proved between the counts is an identity between the coefficients, and an identity proved between the coefficients transports back because the embedding is injective.
Depends on
- The Catalan number $C_n:=\lvert\mathcal{D}_n\rvert$
- Formal power series over a commutative ring and the coefficient-extraction functional $[x^n]$
- Coefficient extraction is $R$-linear, separates formal series, shifts under multiplication by $x^k$, and converts products to finite convolution
- Cauchy multiplication makes $R\llbracket x\rrbracket$ a commutative ring containing $R[x]$ as the finitely supported subring
- Formal exponential, logarithm, and binomial powers over a commutative $\mathbb Q$-algebra
- The rationals form a field
- Every field is a commutative ring with $1 \ne 0$; it is an integral domain, and it is a commutative division ring
- The naturals embed in the integers
- The integers embed in the rationals
- The principle of mathematical induction
Used by
- Motzkin paths, Schröder paths, the Motzkin numbers Mₙ, the large Schröder numbers Rₙ, and their generating functions Definition
- The first coefficients of the Catalan generating function Example
- FALSE: the Catalan numbers satisfy a constant-coefficient linear recurrence False statement
- [xᵏ](1-4x)^1/2=-2/kC(2k-2, k-1) for k≥1, and 1 for k=0 Lemma
- 2x C(x)=1-(1-4x)^1/2, where (1-4x)^1/2 is the unique square root with constant coefficient 1 Theorem
- A third derivation of (n+1) Cₙ=C(2n, n), from the closed form of C(x) Theorem
- C(x) is not a rational formal power series, so (Cₙ) satisfies no eventual constant-coefficient linear recurrence Theorem
- C(x)=1+x C(x)² Theorem
- M(x)=1+x M(x)+x²M(x)², and 2x²M(x)=1-x-(1-2x-3x²)^1/2 Theorem
- R(x)=1+x R(x)+x R(x)², and 2x R(x)=1-x-(1-6x+x²)^1/2 Theorem
Dependency tree · two levels
46 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
- A. Postnikov (notes by A. Lin), MIT 18.212 Algebraic Combinatorics, Spring 2019, Proposition 6 (standard reference, not scraped)
- D. Guichard, An Introduction to Combinatorics and Graph Theory, §3.5 (standard reference, not scraped)