Combinatorics — Between the Lines
From the fundamentals of counting to the connection between DP and generating functions. An eight-part series that answers the questions textbooks leave between the lines, building intuition for combinatorics.
What does it mean to count? Addition, multiplication, and surjections
Counting is the act of measuring the cardinality of a set. Whether you add or multiply depends on whether your set decomposes as a disjoint union or a Cartesian product. From this single viewpoint, permutations, combinations, and the surjection formula all emerge naturally.
The many faces of the binomial coefficient: why nCr is so ubiquitous
Through Pascal's triangle, lattice paths, and the binomial theorem, we uncover the many identities of the binomial coefficient. We also cover the computational machinery essential for competitive programming: factorial tables with modular inverses, and Lucas' theorem for enormous indices.
Inclusion--exclusion: why the alternating signs work
The inclusion--exclusion principle corrects for overcounting by alternately adding and subtracting intersection sizes. We prove the general formula using indicator functions, apply it to count derangements, and trace the thread forward to the Mobius inversion formula on partially ordered sets.
Recurrences and generating functions: what happens when you turn a sequence into a function
A generating function is the "business card" of a sequence. Multiplication becomes convolution, and recurrences become algebraic equations. We derive the closed form for the Fibonacci numbers (Binet's formula) as a showcase of the method.
Why the Catalan numbers appear everywhere: parenthesizations, binary trees, and lattice paths
The Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$ answers questions about balanced parentheses, binary trees, lattice paths, polygon triangulations, and ballot sequences. Through the reflection principle and explicit bijections, we explain why all these problems share the same answer.
The pigeonhole principle: a surprisingly powerful tool for existence proofs
If you place more pigeons than there are holes, some hole must contain at least two pigeons. This triviality is the starting point for the Erdos--Szekeres theorem on monotone subsequences and for Ramsey theory, illustrating the remarkable reach of non-constructive existence arguments.
Counting under symmetry: Burnside's lemma and Polya's enumeration theorem
When objects related by rotation or reflection are considered identical -- as with necklaces -- naive counting fails. Using the language of group actions, Burnside's lemma reduces the problem to a clean formula: the number of distinct objects equals the average number of fixed points across the group.
Combinatorics meets dynamic programming: when counting becomes computation
Dynamic programming is bottom-up evaluation of a recurrence; a generating function is its analytic closed form. We draw the correspondence between the knapsack DP and generating function multiplication, discuss convolution and FFT, and survey the connections across the entire series.