Combination Ontology

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

1. PURPOSE
Model unordered selection of elements from a finite set, with explicit distinction between selections with and without repetition. Provide typed operations, identities, inference and validation for semantic retrieval and mathematical reasoning.

2. TYPED ENTITIES
entity Set<T> { elements: finite distinct T }
entity Natural { value: integer >= 0 }
entity Selection<T> { members: Set<T> }
entity Multiset<T> { multiplicity: T -> Natural; finite_support: true }
entity Combination<T> { universe: Set<T>; size: Natural; selected: Selection<T> }
entity RepeatedCombination<T> { universe: Set<T>; size: Natural; selected: Multiset<T> }
entity BinomialCoefficient { n: Natural; k: Natural; value: Natural }
entity CountingProof { premises: Proposition[]; conclusion: Proposition; rule: Identifier }

3. DEFINITIONS AND TYPE CONSTRAINTS
let S: Set<T>; n := |S|; k: Natural.
Combination(S,k) := { A subseteq S : |A| = k }.
C(n,k) := |Combination(S,k)| for any finite S with |S|=n.
C(n,k) = n! / (k! (n-k)!) for 0 <= k <= n.
C(n,k) = 0 for k > n (extended convention).
0! = 1.
RepeatedCombination(S,k) := { m: S -> Natural : sum_{x in S} m(x)=k }.
For n >= 1, |RepeatedCombination(S,k)| = C(n+k-1,k).
For n=0, repeated combination count is 1 when k=0 and 0 when k>0.
Selection order is irrelevant; each selected element occurs at most once in ordinary combinations.

4. CORE OPERATIONS
op enumerate_combinations(S:Set<T>, k:Natural) -> Set<Selection<T>>
  pre: finite(S)
  post: result = {A subseteq S | |A|=k}
op count_combinations(n:Natural, k:Natural) -> Natural
  post: result = C(n,k)
op enumerate_repeated(S:Set<T>, k:Natural) -> Set<Multiset<T>>
  post: every multiset has support subseteq S and total multiplicity k
op count_repeated(n:Natural, k:Natural) -> Natural
  post: result = (n=0 ? (k=0 ? 1 : 0) : C(n+k-1,k))
op complement_selection(S:Set<T>, A:Selection<T>) -> Selection<T>
  pre: A subseteq S
  post: result = S \ A
op rank_combination(A:Selection<T>, ordering:TotalOrder<T>) -> Natural
  pre: finite universe and A subseteq universe
  post: rank is unique under the specified enumeration convention

5. ALGEBRAIC IDENTITIES
C(n,0)=C(n,n)=1 for n>=0.
C(n,k)=C(n,n-k) for 0<=k<=n.
C(n,k)=C(n-1,k-1)+C(n-1,k) for n>=1, 1<=k<=n-1.
sum_{k=0}^n C(n,k)=2^n.
sum_{k=0}^n (-1)^k C(n,k)=0 for n>=1.
k*C(n,k)=n*C(n-1,k-1) for n>=1, 1<=k<=n.
C(n,k)*C(k,r)=C(n,r)*C(n-r,k-r) for 0<=r<=k<=n.
C(a+b,k)=sum_{i=0}^k C(a,i)*C(b,k-i) for a,b,k>=0, using C(n,k)=0 when k>n.

6. RELATIONSHIPS
Combination --is_a--> UnorderedSelection
Combination --defined_over--> FiniteSet
Combination --has_size--> Natural
Combination --counted_by--> BinomialCoefficient
Combination --contrasts_with--> Permutation
RepeatedCombination --allows--> Repetition
BinomialCoefficient --appears_in--> BinomialTheorem
BinomialCoefficient --satisfies--> PascalIdentity
Combination --supports--> SamplingWithoutReplacement
RepeatedCombination --supports--> SamplingWithReplacementUnordered

7. INFERENCE RULES
rule ORDINARY_COUNT:
  if finite(S) and |S|=n and 0<=k<=n
  then |Combination(S,k)| = C(n,k).
rule IMPOSSIBLE_SELECTION:
  if k>|S| then Combination(S,k) = empty_set.
rule COMPLEMENT_BIJECTION:
  if A subseteq S and |A|=k
  then |S\A|=|S|-k; hence C(n,k)=C(n,n-k).
rule PASCAL_SPLIT:
  if x in S and |S|=n>=1
  then k-subsets partition into those containing x and those excluding x.
rule REPEATED_COUNT:
  if |S|=n>=1 then |RepeatedCombination(S,k)|=C(n+k-1,k).

8. VALIDATION
assert count_combinations(5,2)==10.
assert count_combinations(5,0)==1.
assert count_combinations(3,4)==0.
assert count_repeated(3,2)==6.
assert count_repeated(0,0)==1.
assert count_repeated(0,2)==0.
assert C(6,2)==C(6,4).
assert sum_{k=0}^4 C(4,k)==16.
reject Combination(S,k) when selected contains elements outside S.
reject Combination(S,k) when selected cardinality differs from k.
reject ordinary combinations represented as ordered tuples or as multisets with repeated members.

9. SEMANTIC_EQUIVALENCE
"combination without repetition" == "unordered k-element subset".
"n choose k" == "binomial coefficient C(n,k)".
"combination with repetition" == "unordered multiset selection of size k".
not_equivalent("combination", "permutation") unless context explicitly collapses order and the relevant counts coincide.

10. CONFIDENCE
mathematical_definitions: 1.00
standard_identities: 1.00
page_specific_alignment: unverified
rule: confidence values express formal mathematical certainty within stated assumptions, not empirical model calibration.

11. FLOW_HASH
canonicalise: UTF-8; Unicode NFC; normalise line endings to LF; preserve formula meaning and ordered rule identifiers.
algorithm: SHA-256
value: COMPUTE_ON_PUBLICATION
note: Do not invent a digest before hashing the final canonical payload.

12. UPDATE_MODEL
versioning: semantic-version
triggers: corrected theorem, changed ontology scope, new formal operation, source-page revision
procedure: validate types -> run identities and examples -> check semantic links -> compute FLOW_HASH -> publish with provenance.

13. AI_CONSUMPTION
retrieval_keys: [combination, unordered selection, binomial coefficient, n choose k, repetition, Pascal identity, counting]
reasoning_guardrails:
  - Identify whether order matters before selecting a counting formula.
  - Identify whether repetition is allowed.
  - Require integer n,k>=0 and state boundary conventions.
  - Keep combinations distinct from probabilities and permutations.
  - Distinguish mathematical assertions from unverified source-page claims.
output_contract: typed result + assumptions + formula + verification where applicable.

END FLOW ALGEBRA