Counting, arrangement, and structure of finite discrete objects. Factorials, binomials, pigeonhole, inclusion-exclusion, and canonical sequences (Catalan, Ramsey).
combinatorics
Factorial n!
n! = n · (n-1) · … · 1 with 0! = 1. Counts permutations of n objects.
Permutation P(n,k)
Number of k-length ordered arrangements of n distinct objects: P(n,k) = n! / (n-k)!.
Combination C(n,k) = nCr
Number of k-subsets of an n-set: C(n,k) = n! / (k! (n-k)!). Entries of Pascal's triangle.
Binomial theorem
(a + b)ⁿ = Σ_{k=0..n} C(n,k) a^(n-k) b^k. Generalises Pascal's triangle and grounds generating-function combinatorics.
Pigeonhole principle
If n items are placed in m < n containers, at least one container holds ≥ 2 items. Deceptively powerful; behind many existence proofs.
Inclusion-exclusion principle
|A₁ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + … + (-1)^(n+1) |A₁∩…∩Aₙ|. Canonical tool for counting with overlap.
Catalan numbers C_n
C_n = C(2n,n) / (n+1). Counts balanced-parenthesis strings, binary trees of n internal nodes, non-crossing partitions, and much more.
Ramsey's theorem
For any k, r there is N such that any r-colouring of edges of the complete graph Kₙ (n ≥ N) contains a monochromatic clique of size k.…
λ (Conway's constant)
The growth rate of the length of the 'look-and-say' sequence (Conway, 1986). Algebraic of degree 71; the unique positive real root of the…
Viswanath's constant
The almost-sure exponential growth rate of random Fibonacci sequences f_{n+1} = ±f_n ± f_{n-1} with signs chosen uniformly. Viswanath…
W (Lieb's square-ice constant)
The residual entropy per vertex of the square-ice model (six-vertex model with zero field), solved exactly by Lieb (1967).
Stirling numbers
Two families: S(n,k) (second kind) counts partitions of {1..n} into k non-empty blocks; s(n,k) (first kind, signed) is the coefficient of…
Bell numbers B_n
B_n counts the partitions of an n-set; equivalently Σ_k S(n,k). Exponential generating function e^{e^x − 1}; Dobiński's formula B_n =…
Integer partition
A way of writing n as a sum n = λ_1 + λ_2 + … + λ_k with λ_1 ≥ … ≥ λ_k ≥ 1. The partition function p(n) grows like (1/4n√3) exp(π√(2n/3))…
Young tableau
A filling of a Young diagram shape λ with positive integers, weakly-increasing across rows and strictly-increasing down columns…
Robinson–Schensted–Knuth correspondence
A bijection between N-matrices with finite support and pairs (P,Q) of semistandard Young tableaux of the same shape. Restricts to…
Generating function
A formal (or analytic) series Σ a_n x^n or Σ a_n x^n/n! encoding a combinatorial sequence. Algebraic operations on series mirror…
Schur function
Symmetric polynomial s_λ indexed by a partition λ; basis of the ring of symmetric functions; character of the irreducible…
Matroid
An abstraction of 'independence' unifying linear (vector) and graphic (forest) independence: a finite set E with a family ℐ of independent…
Symmetric function
Formal series f(x_1,x_2,…) invariant under every permutation of variables; the ring Λ has classical bases {m_λ, e_λ, h_λ, p_λ, s_λ} related…
Pólya enumeration theorem
For a finite group G acting on a set X, the number of colourings of X with colour-weight w_c, up to G-action, equals the cycle-index Z_G…
Exponential generating function
EGF A(x) = Σ a_n x^n/n!; product encodes labelled structures; e^{B(x)} counts sets-of-B. Flajolet-Sedgewick symbolic method.
Burnside / Cauchy-Frobenius lemma
# orbits of finite G acting on X = (1/|G|) Σ_g |X^g|. Counts essentially-distinct colorings under symmetry.
Möbius function of a poset
μ(x,y): defining zeta-inverse on incidence algebra. Inversion: f(y) = Σ_{x≤y} g(x) ⟺ g(y) = Σ_{x≤y} μ(x,y) f(x). Rota.
Stirling numbers of 1st/2nd kind
c(n,k) signed = coeffs of x(x−1)…(x−n+1); S(n,k) = # partitions of n into k non-empty blocks. Pascal-like recurrences.
Bell numbers & Dobinski formula
B_n = # partitions of n-set = Σ_k S(n,k). EGF e^{e^x − 1}. Dobinski: B_n = (1/e) Σ_{k≥0} kⁿ/k!.
Catalan numbers
C_n = (1/(n+1)) C(2n,n). Counts Dyck paths, binary trees, triangulations, non-crossing matchings. Generating function 1−√(1−4x))/(2x).
Szemerédi's theorem
Subset of ℤ with positive upper density contains arithmetic progressions of every length. Szemerédi 1975; Furstenberg via ergodic; Gowers…
Erdős-Ko-Rado theorem
Intersecting family of k-subsets of [n] (n ≥ 2k): |F| ≤ C(n−1, k−1), extremal = stars. Cornerstone of extremal set theory.
Ramsey's theorem (finite/infinite)
Any 2-coloring of edges of K_N contains monochromatic K_n for N ≥ R(n). Hales-Jewett cube; canonical Ramsey; structural.
Matroid
Combinatorial abstraction of linear independence: set E with independence family satisfying hereditary + exchange axioms. Greedy algorithm…
Probabilistic method (Erdős)
Existence proofs via positive probability of object. Ramsey lower bounds R(n,n) ≥ 2^{n/2}; Lovász Local Lemma. Non-constructive power.
Cayley's formula
The number of labeled trees on n vertices equals n^{n−2}. Proved by Cayley 1889; Prüfer 1918 gave the bijection with length-(n−2) sequences…
Dilworth's theorem
In any finite poset P, the minimum number of chains needed to partition P equals the maximum size of an antichain (the width w(P)). …
Mirsky's theorem
Dual to Dilworth: in any finite poset, the minimum number of antichains needed to partition P equals the maximum length of a chain (the…
Erdős-Szekeres theorem
Any sequence of (r−1)(s−1) + 1 distinct reals contains a monotone subsequence: either increasing of length r or decreasing of length s. …
Van der Waerden's theorem
For any r, k there exists W(r, k) such that every r-colouring of {1, …, W(r, k)} contains a monochromatic arithmetic progression of length…
Schur's partition theorem
For every r, there exists S(r) such that any r-colouring of {1, …, S(r)} contains monochromatic x, y, x + y. Exact values: S(1)=2, S(2)=5,…
Sperner / LYM inequality
Sperner 1928: the largest antichain in the Boolean lattice 2^[n] has size C(n, ⌊n/2⌋) (the middle layer). LYM (Lubell-Yamamoto-Meshalkin)…
Lucas' theorem (binomial coefficients)
For prime p and non-negative m, n, the binomial coefficient C(m, n) mod p equals the product of 'digit-wise' binomial coefficients C(m_i,…