Combinatorics

Counting identities plus the probabilistic and extremal methods built on them.

Counting & Identities

Binomial Theorem — (a+b)^n = _k nk a^n-k b^k — coefficients come from choices.
Vandermonde's Identity — m+nr = _k mk nr-k — split the committee by team.
Catalan Numbers — C_n = 1/n+1 2nn — balanced parens, binary trees, Dyck paths.
Generating Functions — Pack a sequence into one power series — the geometric series does the work.
Ramsey's Theorem — R(s, t) ≤ R(s-1, t) + R(s, t-1): Ramsey's theorem by induction.

Turán's Theorem — Max edges with no K_r+1: (1 - 1/r) · n^2/2, uniquely achieved by the balanced complete r-partite graph.
Expander Mixing Lemma — |e(S, T) - d|S||T|/n| ≤ λ √|S||T| — spectral gap controls pseudorandomness.
Lovász Local Lemma — When bad events are sparsely dependent, some outcome avoids them all: ep(d+1) ≤ 1 forces P( A_i) > 0.

Derangements — Permutations with no fixed point, via inclusion-exclusion and the e^-1 limit.
Stirling Numbers and the Twelvefold Way — Partitions, surjections, and cycles in the twelvefold way.
Mobius Inversion on Posets — The Mobius function and the poset generalization of inclusion-exclusion.
Dilworth's Theorem — Minimum chain cover equals maximum antichain in any finite poset.
Sperner's Theorem — The largest antichain in the Boolean lattice is the middle layer.
Van der Waerden's Theorem — Long colorings force monochromatic arithmetic progressions.
Sperner's Lemma — Three colors on a triangulated triangle force a fully colored cell.