Binomial Coefficient Ontology

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

1. PURPOSE
Model binomial coefficients as exact combinatorial quantities, with typed operands, valid identities, computable transformations, proof obligations and machine-consumable semantics.

2. TYPED ENTITIES
NaturalNumber := integer n >= 0
Index := integer k
BinomialCoefficient(n: NaturalNumber, k: Index) -> NaturalNumber
FiniteSet(n): a set with cardinality n
SubsetSelection(S, k): {T subseteq S : |T| = k}
Factorial(n): product of integers from 1 to n, with 0! = 1
PascalTriangleRow(n): [C(n,0), ..., C(n,n)]
GeneratingPolynomial(n,x): (1+x)^n

3. CORE DEFINITION
For n >= 0 and 0 <= k <= n:
  C(n,k) = n! / (k! (n-k)!)
For n >= 0 and k < 0 or k > n:
  C(n,k) = 0
COMBINATORIAL_MEANING:
  C(n,k) = |SubsetSelection(S,k)| whenever |S| = n.
Ordering of selected elements does not matter; elements are distinct.

4. ALGEBRAIC RULES
BOUNDARIES: C(n,0) = C(n,n) = 1.
SYMMETRY: C(n,k) = C(n,n-k) for 0 <= k <= n.
PASCAL: C(n,k) = C(n-1,k-1) + C(n-1,k) for n >= 1 and all integer k.
ROW_SUM: sum_{k=0}^n C(n,k) = 2^n.
ALTERNATING_SUM: sum_{k=0}^n (-1)^k C(n,k) = 0 for n >= 1; equals 1 for n=0.
WEIGHTED_SUM: sum_{k=0}^n k*C(n,k) = n*2^(n-1) for n >= 1; equals 0 for n=0.
ABSORPTION: k*C(n,k) = n*C(n-1,k-1) for n >= 1, 1 <= k <= n.
VANDERMONDE: C(r+s,n) = sum_{k=0}^n C(r,k)*C(s,n-k) for r,s,n >= 0.
BINOMIAL_THEOREM: (a+b)^n = sum_{k=0}^n C(n,k)*a^(n-k)*b^k for n >= 0 in a commutative ring.

5. FLOW OPERATIONS
flow BINOMIAL(n,k):
  require integer(n) and integer(k) and n >= 0
  if k < 0 or k > n: return 0
  m := min(k,n-k)
  result := 1
  for i from 1 through m:
    result := (result * (n-m+i)) / i
  return exact_integer(result)

flow ENUMERATE_SUBSETS(S,k):
  require finite(S) and integer(k)
  return {T subseteq S where |T| = k}

flow VERIFY_COUNT(S,k):
  require finite(S) and integer(k)
  return |ENUMERATE_SUBSETS(S,k)| == BINOMIAL(|S|,k)

6. RELATIONSHIPS
BinomialCoefficient IS_A CombinatorialCount
BinomialCoefficient COUNTS UnorderedDistinctSelections
BinomialCoefficient IS_COEFFICIENT_OF BinomialExpansion
BinomialCoefficient FORMS PascalTriangle
BinomialCoefficient RELATES_TO PermutationCount
BinomialCoefficient RELATES_TO ProbabilityAndBinomialDistribution
PascalIdentity DERIVES_FROM SubsetPartitionByDistinguishedElement

7. INFERENCE RULES
IF |S|=n AND 0<=k<=n THEN |{T subseteq S:|T|=k}|=C(n,k).
IF a subset T of S has k elements THEN its complement in S has n-k elements; infer C(n,k)=C(n,n-k).
IF n>=1 AND k integer THEN partition k-subsets by membership of one distinguished element to infer Pascal's identity.
IF two independent disjoint finite sets have sizes r and s THEN count n-selections by their split to infer Vandermonde's identity.

8. VALIDATION
CHECK n is non-negative integer and k is integer.
CHECK output is a non-negative exact integer.
CHECK C(0,0)=1; C(5,2)=10; C(6,3)=20; C(5,7)=0.
CHECK symmetry and Pascal recurrence across representative inputs.
CHECK sum of row n equals 2^n.
Do not treat selections with replacement as C(n,k); their count is C(n+k-1,k) for n>=1, k>=0.
Do not assume factorial quotient is safe in floating-point arithmetic for large inputs.

9. SEMANTIC_EQUIVALENCE
"n choose k" == "C(n,k)" == "binomial coefficient n over k".
"number of k-element subsets of an n-element set" == C(n,k).
Not equivalent to nPk = n!/(n-k)! (ordered arrangements).

10. CONFIDENCE
Formal mathematical definitions and identities: 1.00 within stated assumptions.
External page alignment: unverified; do not infer a measured confidence score.

11. FLOW_HASH
METHOD: SHA-256 over canonical UTF-8 normalised flow content.
VALUE: COMPUTE_ON_INGEST (not a fabricated digest).

12. UPDATE_MODEL
Trigger: change in formal definitions, notation, validation rules, source text or ontology relationships.
Process: verify assumptions -> revise version -> run identities and boundary tests -> regenerate FLOW_HASH -> publish provenance.

13. AI_CONSUMPTION
Inputs: n: non-negative integer; k: integer; optional finite set S.
Outputs: exact count, derivation trace, semantic relationships and validation status.
Guarantees: deterministic arithmetic for valid inputs; zero outside 0<=k<=n.
Safety: preserve integer exactness and explicit mathematical preconditions.

END FLOW ALGEBRA