# Combinatorics

**Type:** Concept  
**Domain:** Discrete Mathematics  
**Codex URL:** /mathematics/discrete/combinatorics/  
**Entry status:** Live — v1.0 (2026-05-27)

## Summary
The mathematics of counting: arrangements, selections, combinations. Essential to probability, cryptography, algorithm analysis.

## Permutations and combinations
P(n,k) = n!/(n−k)! — order matters
C(n,k) = n!/[k!(n−k)!] — order doesn't matter ("n choose k")

## Pascal's Triangle
Multi-civilisational: China (Yang Hui, 1261), Persia (Al-Karaji, c.1000), India (Piṅgala, earlier) — predates Pascal's 17th-century European treatment.

## Pigeonhole Principle
n+1 items in n containers → some container has 2+. Example: 367 people guarantee a shared birthday.

## Ramsey theory
Complete disorder is impossible in sufficiently large structures. R(5,5) remains unknown; Erdős's alien-invasion anecdote illustrates the extreme computational difficulty.

## Probabilistic method (Erdős)
Proves existence of objects with desired properties by showing a random object has positive probability of having them — non-constructive but powerful.

## Sources
### Tier 1
- Stanley, R.P. (2011). *Enumerative Combinatorics*. Vol. 1, 2nd ed.
- Graham, R.L., Knuth, D.E. and Patashnik, O. (1994). *Concrete Mathematics*. 2nd ed.
### Tier 2
- Graham, R.L., Rothschild, B.L. and Spencer, J.H. (1990). *Ramsey Theory*. 2nd ed.

---
*Mathematics Codex entry v1.0 — added 2026-05-27 — thecodex.expert/mathematics/*