Catalan Number Ontology

FLOW ALGEBRA
TITLE: Catalan Number Ontology
DOMAIN: Discrete Mathematics / Combinatorics
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/combinatorics/catalan-number-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Mathematical synthesis; live page not independently verified.

1. PURPOSE
Model Catalan numbers as a typed combinatorial sequence with exact counting interpretations, recurrences, generating functions, identities, inference rules and machine-checkable validation.

2. TYPED ENTITIES
NaturalNumber := integer n >= 0
PositiveInteger := integer n >= 1
CatalanNumber := nonnegative integer C(n)
BinomialCoefficient := choose(n,k), defined for integers 0 <= k <= n
DyckPath := lattice path from (0,0) to (2n,0) with n up-steps and n down-steps, never below height zero
BalancedParenthesisWord := balanced word with n matching pairs
FullBinaryTree := rooted ordered tree where each internal node has exactly two children
PolygonTriangulation := triangulation of a convex (n+2)-gon, for n >= 1
FormalPowerSeries := series over rational or integer coefficients

3. CANONICAL DEFINITIONS
C(0) = 1
C(n) = choose(2n,n)/(n+1), for n >= 0
C(n) = (2n)! / (n! (n+1)!), for n >= 0
C(n+1) = sum_{i=0}^{n} C(i)*C(n-i), for n >= 0
C(n+1) = [2*(2*n+1)/(n+2)]*C(n), for n >= 0
Initial terms: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796.

4. SEMANTIC RELATIONSHIPS
CatalanNumber IS_A CombinatorialCountingSequence
CatalanNumber COUNTS DyckPath with semilength n
CatalanNumber COUNTS BalancedParenthesisWord with n pairs
CatalanNumber COUNTS FullBinaryTree with n internal nodes
CatalanNumber COUNTS triangulations of convex (n+2)-gon for n >= 1
CatalanNumber DERIVED_FROM BinomialCoefficient
CatalanNumber SATISFIES QuadraticRecurrence
CatalanNumber HAS_GENERATING_FUNCTION CatalanGeneratingFunction
CatalanNumber RELATED_TO BinaryTreeOntology, PathOntology, RecurrenceRelationOntology, GeneratingFunctionOntology, BinomialCoefficientOntology

5. FLOW OPERATIONS
flow CatalanClosedForm(n:NaturalNumber) -> CatalanNumber:
  return choose(2*n,n) // (n+1)  # exact division

flow CatalanRecurrence(n:NaturalNumber) -> CatalanNumber:
  if n == 0: return 1
  return sum(CatalanRecurrence(i)*CatalanRecurrence(n-1-i) for i in 0..n-1)

flow CountDyckPaths(n:NaturalNumber) -> NaturalNumber:
  return CatalanClosedForm(n)

flow IsCatalanCandidate(n:NaturalNumber, value:integer) -> boolean:
  return value == CatalanClosedForm(n)

6. GENERATING FUNCTION
C(x) = sum_{n>=0} C(n)*x^n
C(x) = 1 + x*C(x)^2
C(x) = (1 - sqrt(1-4*x))/(2*x), interpreted by its removable singularity at x=0, C(0)=1
Formal power-series interpretation is primary; analytic radius of convergence = 1/4.

7. ALGEBRAIC LAWS AND INVARIANTS
C(n) is a positive integer for all n >= 0.
C(0) = C(1) = 1; C(n+1) > C(n) for n >= 1.
C(n) = choose(2*n,n) - choose(2*n,n+1).
C(n) ~ 4^n / (sqrt(pi)*n^(3/2)) as n tends to infinity.
For n >= 0: sum_{i=0}^n C(i)*C(n-i) = C(n+1).

8. INFERENCE RULES
IF a structure is a balanced parenthesis word with n pairs THEN its class cardinality is C(n).
IF a rooted ordered full binary tree has n internal nodes THEN its class cardinality is C(n).
IF a Dyck path has semilength n THEN its class cardinality is C(n).
IF a convex polygon has n+2 vertices and n >= 1 THEN its triangulation count is C(n).
IF a proposed C(n) differs from the exact closed form THEN flag validation failure.

9. VALIDATION
Require n to be a nonnegative integer.
Use arbitrary-precision integers for factorials and binomial coefficients.
Cross-check recurrence against closed form for n=0..20.
Test n=0 -> 1; n=1 -> 1; n=2 -> 2; n=3 -> 5; n=4 -> 14; n=5 -> 42.
Ensure CatalanClosedForm performs exact integer division.
Reject nonintegral or negative proposed Catalan values.
Distinguish trees counted by internal nodes from trees counted by total vertices.

10. SEMANTIC_EQUIVALENCE
"Catalan number C_n" == "nth Catalan number" under the zero-based convention C_0=1.
"Balanced bracket strings with n pairs" == "balanced parenthesis words with n pairs" for one bracket type.
"Dyck paths of semilength n" == "Dyck paths with 2n steps".
Equivalence is contextual: other indexing conventions must be explicitly normalised.

11. CONFIDENCE
Formal definitions, identities and counting correspondences: 1.00 (mathematically established).
Interpretation of the source page: unverified; no page-specific claims asserted.
Confidence scores are metadata, not probabilities of mathematical truth.

12. FLOW_HASH
Canonicalise: UTF-8; LF line endings; stable key order; normalise whitespace outside quoted values.
FLOW_HASH := SHA-256(canonicalised flow payload excluding FLOW_HASH field).
No hash value is asserted until the final payload is canonicalised and hashed.

13. UPDATE_MODEL
Update on corrected mathematical definitions, added validated identities, source revisions or ontology relationship changes.
Record version, change reason, author, date and recalculated FLOW_HASH.
Preserve earlier versions for provenance.

14. AI_CONSUMPTION
Represent C(n) as an exact integer indexed from zero.
Expose formula, recurrence, generating function, combinatorial interpretations and validation rules as separate machine-readable facts.
Require explicit indexing and structural-size conventions before matching external data.
Use symbolic algebra or integer arithmetic rather than floating-point approximation for exact outputs.

END FLOW ALGEBRA