Combinatorics
Pigeonhole Principle
If n+1 objects are placed into n boxes, some box contains at least two objects
Inclusion-Exclusion Principle
The size of a union is the alternating sum of intersection sizes
Catalan Numbers
The ubiquitous sequence counting balanced parentheses, binary trees, and Dyck paths
Stirling Numbers
Counting partitions of n elements into k non-empty subsets
Bell Numbers
The total number of partitions of a set of n elements
Pascal's Identity
The binomial coefficient recurrence: C(n,k) = C(n-1,k-1) + C(n-1,k), the engine of Pascal's triangle.
Orbit Counting Applications
Necklace, bracelet, and coloring counting via Burnside's lemma — concrete applications of the orbit-counting formula.
Vandermonde's Identity
The convolution identity for binomial coefficients: C(m+n,r) = sum over k of C(m,k)*C(n,r-k).
Chu-Vandermonde Identity
The upper negation generalization of Vandermonde's identity to upper complex parameters via rising factorials.
Ramsey's Theorem
Any 2-coloring of K_6 contains a monochromatic triangle: the Ramsey bound R(3,3) <= 6.
Erdos-Ko-Rado Theorem
The maximum intersecting family of k-subsets of an n-set has size C(n-1,k-1) when n >= 2k.
Polya Enumeration
The cycle index polynomial encodes all Burnside fixed-point counts into one generating function for weighted orbit counting.
Stirling's Approximation
The asymptotic formula n! ~ sqrt(2*pi*n) * (n/e)^n, with the Mathlib proof that n!/stirling(n) tends to 1.