Combinatorics Ontology

FLOW ALGEBRA
TITLE: Combinatorics Ontology
DOMAIN: Discrete Mathematics / Combinatorics
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/combinatorics/combinatorics-ontology.html
VERSION: 1.0
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
SOURCE_STATUS: Domain-grounded mathematical model; live page not independently verified.

1. PURPOSE
Model finite counting, arrangements, selections, partitions, and discrete structures with typed entities, constraints, derivations, and validation rules. Explicitly distinguish ordered from unordered and replacement from no-replacement counting.

2. TYPE SYSTEM
TYPE Set[T] = finite collection of distinct elements of type T
TYPE Sequence[T] = ordered finite list of elements of type T
TYPE Multiset[T] = finite collection with nonnegative integer multiplicities
TYPE Natural = {0,1,2,...}
TYPE PositiveNatural = {1,2,...}
TYPE Count = Natural
TYPE Proposition = Boolean-valued mathematical assertion
TYPE CountingProblem = {universe, constraints, order_matters, repetition_allowed, target}
TYPE EnumerationResult[T] = {objects: Set[T], count: Natural, completeness_proof?}
TYPE ProofCertificate = {assumptions, rule, conclusion, verification}

3. CORE ENTITIES AND RELATIONSHIPS
ENTITY Combinatorics: mathematical study of finite discrete structures and counting
ENTITY Permutation: ordered arrangement of distinct elements, unless multiset specified
ENTITY Combination: unordered selection
ENTITY Partition: family of nonempty, pairwise disjoint blocks covering a set
ENTITY Recurrence: rule defining sequence terms from earlier terms
ENTITY GeneratingFunction: formal power series encoding sequence coefficients
ENTITY Bijection: invertible correspondence between finite sets
RELATION is_subfield_of(Combinatorics, DiscreteMathematics)
RELATION counted_by(CountingProblem, Count)
RELATION justified_by(Count, ProofCertificate)
RELATION encoded_by(Sequence[Count], GeneratingFunction)

4. OPERATIONS
OP factorial(n: Natural) -> PositiveNatural:
  0! = 1; n! = product(i=1..n, i) for n >= 1
OP falling_factorial(n: Natural, k: Natural) -> Natural:
  PRE 0 <= k <= n
  RESULT n!/(n-k)!
OP permutations(n: Natural, k: Natural) -> Natural:
  PRE 0 <= k <= n
  RESULT falling_factorial(n,k)
OP combinations(n: Natural, k: Natural) -> Natural:
  PRE 0 <= k <= n
  RESULT n!/(k!*(n-k)!)
OP sequences_with_replacement(n: Natural, k: Natural) -> Natural:
  RESULT n^k; adopt 0^0 = 1 for the unique empty sequence
OP multisets_of_size(n: PositiveNatural, k: Natural) -> Natural:
  RESULT combinations(n+k-1,k)
OP powerset_count(n: Natural) -> Natural:
  RESULT 2^n
OP derangements(n: Natural) -> Natural:
  RESULT n! * sum(j=0..n, (-1)^j/j!)
OP partitions_into_blocks(n: Natural, k: Natural) -> Natural:
  RESULT StirlingSecondKind(n,k)

5. FLOW RULES
FLOW ClassifyCountingProblem:
  INPUT CountingProblem P
  CHECK finite universe and explicit constraints
  BRANCH ordered + no repetition -> permutations
  BRANCH unordered + no repetition -> combinations
  BRANCH ordered + repetition -> sequences_with_replacement
  BRANCH unordered + repetition -> multisets_of_size
  OTHERWISE -> constraint-aware enumeration or bijective reduction
  OUTPUT {method, count, proof_certificate}

FLOW SumRule:
  INPUT pairwise disjoint finite sets A1,...,Am
  OUTPUT |union(Ai)| = sum(|Ai|)
  VALIDATE disjointness

FLOW ProductRule:
  INPUT finite choice sets A1,...,Am with independent stage options
  OUTPUT |A1 x ... x Am| = product(|Ai|)

FLOW BijectionRule:
  INPUT finite sets A,B and function f:A->B
  REQUIRE injective(f) AND surjective(f)
  INFER |A| = |B|

FLOW InclusionExclusion:
  INPUT finite sets A1,...,Am
  OUTPUT |union(Ai)| = sum over nonempty J subseteq {1..m} of (-1)^(|J|+1) * |intersection(Aj for j in J)|

FLOW Pigeonhole:
  INPUT n objects, k boxes, k>0
  INFER some box contains at least ceil(n/k) objects

6. ALGEBRAIC LAWS
LAW C(n,k) = C(n,n-k) for 0<=k<=n
LAW C(n,k) = C(n-1,k-1)+C(n-1,k) for 1<=k<=n-1
LAW sum(k=0..n, C(n,k)) = 2^n
LAW sum(k=0..n, (-1)^k*C(n,k)) = 0 for n>0
LAW (x+y)^n = sum(k=0..n, C(n,k)*x^(n-k)*y^k)
LAW S(n,k) = k*S(n-1,k)+S(n-1,k-1) for n>=1, 1<=k<=n
BOUNDARY S(0,0)=1; S(n,0)=0 for n>0; S(0,k)=0 for k>0

7. GENERATING FUNCTIONS
DEFINE A(x) = sum(n>=0, a_n*x^n) as a formal power series
RULE coefficient(A+B,n) = a_n+b_n
RULE coefficient(A*B,n) = sum(k=0..n,a_k*b_(n-k))
EXAMPLE (1+x)^n encodes binomial coefficients for nonnegative integer n
NOTE formal power series identities do not require analytic convergence

8. INFERENCE AND SEMANTIC EQUIVALENCE
INFER count_by_bijection(A,B) IF bijection(A,B)
INFER equivalent_counting_formulations(P,Q) IF certified_bijection(solution_set(P),solution_set(Q))
SEMANTIC_EQUIVALENCE:
  "choose k from n" <-> unordered selection without replacement, only if context confirms
  "arrange k of n" <-> ordered selection without replacement, only if context confirms
  "combination" != "permutation" generally
  "partition of a set" != "integer partition"
  "sampling with replacement" != "sampling without replacement"

9. VALIDATION
CHECK counts are nonnegative integers
CHECK n,k satisfy operator preconditions
CHECK no unproved independence assumption in product-rule applications
CHECK no unproved disjointness assumption in sum-rule applications
CHECK order and repetition flags match counting method
CHECK enumeration and symbolic counts agree on small test instances
CHECK proof certificates for bijection, recurrence, and inclusion-exclusion
TEST C(5,2)=10
TEST P(5,2)=20
TEST 2^3=8
TEST S(3,2)=3
TEST derangements(3)=2

10. CONFIDENCE
CONFIDENCE:
  mathematical_definition: 1.0 when axioms and preconditions hold
  derived_count: 1.0 when proof certificate validates
  heuristic_classification: conditional; requires context confirmation
  source_page_alignment: unverified
  interpretation: confidence is evidence-qualified metadata, not a substitute for proof

11. FLOW_HASH
FLOW_HASH:
  algorithm: SHA-256
  input: canonical UTF-8 representation of flow body excluding computed hash field
  status: compute on ingestion; no fabricated digest

12. UPDATE_MODEL
UPDATE_MODEL:
  trigger: source revision, corrected theorem, changed ontology relationships, or new validation test
  procedure: version change -> validate typing -> rerun tests -> recompute FLOW_HASH -> retain provenance
  backward_compatibility: preserve identifiers or document migration

13. AI_CONSUMPTION
AI_CONSUMPTION:
  machine_readable: true
  reasoning_modes: [symbolic_counting, proof_checking, constraint_solving, ontology_alignment]
  required_inputs: [universe, constraints, order_matters, repetition_allowed]
  expected_outputs: [method, result, assumptions, proof_certificate, confidence]
  safeguards: [do_not_conflate_ordering, do_not_assume_independence, validate_preconditions, disclose_uncertainty]

END FLOW ALGEBRA