Generating Function Ontology

FLOW ALGEBRA
TITLE: Generating Function Ontology
DOMAIN: Discrete Mathematics / Combinatorics
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/combinatorics/generating-function-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Mathematical synthesis; live webpage not independently verified.

1. PURPOSE
Represent generating functions as formal power series that encode sequences, support coefficient extraction, solve recurrence relations, and model combinatorial counting.

2. TYPED ENTITIES
Sequence: a : N_0 -> R
Coefficient: a_n : R
Indeterminate: x : FormalVariable
FormalPowerSeries: R[[x]]
OrdinaryGeneratingFunction: A(x) = sum_{n>=0} a_n x^n
ExponentialGeneratingFunction: E(x) = sum_{n>=0} a_n x^n/n! (R contains Q)
BivariateGeneratingFunction: F(x,y) = sum_{i,j>=0} a_{i,j} x^i y^j
CoefficientExtraction: [x^n]A(x) = a_n
Recurrence: rule relating sequence terms
CombinatorialClass: finite objects grouped by size
SizeFunction: size : Object -> N_0

3. CORE RELATIONSHIPS
ENCODES(GeneratingFunction, Sequence)
HAS_COEFFICIENT(GeneratingFunction, Index, Coefficient)
COUNTS(CombinatorialClass, Size, Cardinality)
EXTRACTS(CoefficientExtraction, GeneratingFunction, Coefficient)
SOLVES(GeneratingFunctionMethod, Recurrence)
TRANSFORMS(GeneratingFunctionOperation, SequenceOperation)

4. FORMAL DEFINITIONS
OGF(a)(x) := sum_{n>=0} a_n x^n in R[[x]].
EGF(a)(x) := sum_{n>=0} (a_n/n!) x^n in R[[x]], where n! is invertible.
[x^n]A(x) := a_n.
Equality: A(x)=B(x) iff for every n>=0, [x^n]A=[x^n]B.
Formal operations do not require analytic convergence.

5. ALGEBRAIC OPERATIONS
Addition: [x^n](A+B) = a_n+b_n.
Scalar multiplication: [x^n](cA)=c*a_n.
Cauchy product: [x^n](AB)=sum_{k=0}^n a_k*b_{n-k}.
Shift: [x^n](x^m A)=a_{n-m} for n>=m; otherwise 0.
Formal derivative: A'(x)=sum_{n>=0}(n+1)a_{n+1}x^n.
Formal integral (Q-algebra): integral A dx = sum_{n>=0} a_n*x^{n+1}/(n+1), with zero constant.
Multiplicative inverse: A(x) is invertible in R[[x]] iff a_0 is a unit in R.
Composition: A(B(x)) is well-defined formally when B(0)=0 (or under additional suitable conditions).

6. COMBINATORIAL IDENTITIES
Geometric series: 1/(1-x) = sum_{n>=0} x^n.
Weighted geometric series: 1/(1-cx)=sum_{n>=0} c^n x^n.
Binomial series: (1-x)^(-r) = sum_{n>=0} binom(n+r-1,r-1)x^n for integer r>=1.
Finite sequence convolution corresponds to OGF multiplication.
For labelled structures under standard exponential combinatorial conventions, product constructions correspond to EGF multiplication with binomial allocation of labels.

7. RECURRENCE EXAMPLE
Fibonacci: F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2} for n>=2.
OGF F(x)=sum_{n>=0}F_n*x^n = x/(1-x-x^2).
Verification: (1-x-x^2)F(x)=x as a formal series.

8. INFERENCE RULES
IF A=OGF(a) AND B=OGF(b) THEN A+B=OGF(a+b).
IF C=A*B THEN c_n=sum_{k=0}^n a_k*b_{n-k}.
IF A=B AS FORMAL SERIES THEN forall n, a_n=b_n.
IF a_0 IS A UNIT THEN EXISTS UNIQUE B WITH A*B=1.
IF a_0=0 AND R IS A FIELD THEN A HAS NO MULTIPLICATIVE INVERSE.
IF A SATISFIES AN ALGEBRAIC EQUATION THEN CHECK INITIAL CONDITIONS TO SELECT THE INTENDED FORMAL SERIES SOLUTION.

9. SEMANTIC_EQUIVALENCE
ordinary generating function <=> OGF
exponential generating function <=> EGF
coefficient of x^n <=> [x^n] operator
Cauchy product <=> convolution of coefficient sequences
NOTE: OGF and EGF are not interchangeable; their normalisations differ.

10. VALIDATION
CHECK coefficient indexing begins at n=0 unless declared otherwise.
CHECK coefficient ring and invertibility assumptions.
CHECK finite coefficient dependence for each formal product.
CHECK initial conditions for recurrence solutions.
CHECK combinatorial class is locally finite: finitely many objects of each size.
CHECK analytic convergence claims separately from formal identities.
CHECK denominator and composition constraints.
REJECT unqualified EGF division by n! in rings where n! is not invertible.

11. CONFIDENCE
Mathematical definitions and standard identities: HIGH.
Application-specific combinatorial interpretations: CONDITIONAL on modelling assumptions.
Live-page correspondence: UNVERIFIED.

12. FLOW_HASH
ALGORITHM: SHA-256
CANONICALISATION: UTF-8; LF line endings; normalise fields and sort relationship triples.
VALUE: COMPUTE_ON_INGEST (not a fabricated digest).

13. UPDATE_MODEL
ON source revision: compare definitions, notation, axioms and examples.
ON mathematical correction: increment version, regenerate derived relations, recompute FLOW_HASH.
PRESERVE source URL, authorship, timestamp and revision history.

14. AI_CONSUMPTION
INPUT: sequence, recurrence, combinatorial class or formal power series.
PROCESS: validate coefficient domain -> choose OGF/EGF -> construct series -> transform algebraically -> extract coefficients -> verify constraints.
OUTPUT: symbolic series, coefficients, proof obligations, assumptions and provenance.
DO_NOT_INFER: convergence, closed form or numerical stability without separate justification.

END FLOW ALGEBRA