Learn combinatorics: the best books to read in order
This curriculum builds a deep mastery of combinatorics starting from a solid intermediate foundation, progressing through core counting techniques, generating functions, and graph-theoretic combinatorics, and culminating in advanced enumeration theory and research-level topics. Each stage sharpens the tools introduced in the previous one, so that by the end the reader can tackle competition mathematics, graduate coursework, and combinatorial research with confidence.
Core Foundations
IntermediateBuild a firm grasp of permutations, combinations, the pigeonhole principle, inclusion-exclusion, and basic recursion — the essential vocabulary for everything that follows.
▸ Study plan for this stage
Pace: 6–8 weeks, ~40–50 pages/day (alternating between Cameron and Bona for variety and reinforcement)
- Permutations and their counting: factorials, arrangements with and without repetition
- Combinations and binomial coefficients: choosing subsets, Pascal's triangle, and symmetry properties
- The Pigeonhole Principle: statement, applications, and generalized forms
- Inclusion-Exclusion Principle: counting with overlapping sets, derangements, and surjections
- Basic recursion and recurrence relations: setting up and solving simple recurrences
- Fundamental counting principles: multiplication rule, addition rule, and when to apply each
- How do you distinguish between a permutation problem and a combination problem, and what is the formula for each?
- State the Pigeonhole Principle and give three distinct real-world applications.
- Explain the Inclusion-Exclusion Principle and use it to count derangements of n objects.
- What is a recurrence relation, and how do you solve one using characteristic equations or iteration?
- How does Pascal's triangle relate to binomial coefficients, and what combinatorial identities can you derive from it?
- Given an overlapping counting problem, how would you use Inclusion-Exclusion to avoid double-counting?
- Work through 15–20 permutation and combination problems from Cameron's exercises, focusing on problems with constraints (e.g., 'arrange n objects where certain pairs must be adjacent').
- Solve at least 10 Pigeonhole Principle problems of increasing difficulty, including at least 3 that require the generalized form.
- Derive the formula for derangements using Inclusion-Exclusion, then compute D(n) for n = 1 to 7 by hand.
- Set up and solve 8–10 recurrence relations from Bona's sections, using both iteration and characteristic equation methods.
- Construct Pascal's triangle to row 12 and verify at least 5 binomial identities (e.g., C(n,k) = C(n,n−k), hockey-stick identity).
- Create a 'decision tree' for 5 mixed counting problems that clarifies which principle(s) apply and why.
Next up: Mastery of these foundational tools—permutations, combinations, the Pigeonhole and Inclusion-Exclusion principles, and recursion—equips you to tackle advanced topics like generating functions, graph coloring, and asymptotic analysis, where these building blocks become the language of proof and problem-solving.
A rigorous yet accessible survey of the entire combinatorics landscape; reading it first gives the learner a reliable map of the field and introduces key terminology cleanly.
Methodically develops counting from first principles through bijections and recursion, with excellent problem sets that cement intuition before moving to harder machinery.
Generating Functions & Enumeration
IntermediateMaster ordinary and exponential generating functions, recurrence relations, and the foundational techniques of systematic enumeration.
▸ Study plan for this stage
Pace: 8–10 weeks, ~25–30 pages/day (Generatingfunctionology: weeks 1–4; Concrete Mathematics relevant chapters: weeks 5–10)
- Ordinary generating functions (OGFs): definition, manipulation, and extraction of coefficients to solve counting problems
- Exponential generating functions (EGFs): when and why to use them for permutations, labeled structures, and combinatorial objects with order
- Recurrence relations: deriving them from combinatorial problems and solving them via generating functions
- Partial fractions and closed-form extraction: converting generating functions back into explicit formulas
- The transfer matrix method and linear recurrences: systematic enumeration of constrained sequences
- Convolution and product rules for generating functions: combining independent and dependent counting problems
- Asymptotic analysis and singularity analysis: extracting growth rates and approximate counts from generating functions
- What is the generating function for the Fibonacci sequence, and how do you extract the nth Fibonacci number from it?
- When should you use an exponential generating function instead of an ordinary one? Give an example.
- How do you set up and solve a recurrence relation using generating functions?
- Explain the convolution rule: if F(x) = Σ f_n x^n and G(x) = Σ g_n x^n, what does the product F(x)G(x) count?
- What is the transfer matrix method, and how does it enumerate sequences with forbidden patterns or constraints?
- Given a generating function with a singularity at x = r, how can you estimate the growth rate of its coefficients?
- Derive the OGF for the number of compositions of n (ordered partitions), verify it matches the closed form 2^(n-1), and extract coefficients for n = 1 to 5
- Write down the EGF for permutations and derangements; confirm that the coefficient of x^n/n! in e^x gives 1 (all permutations) and use it to compute derangements for n = 3, 4, 5
- Solve the recurrence a_n = 3a_(n-1) - 2a_(n-2) with a_0 = 1, a_1 = 3 using generating functions; verify your answer against direct computation
- Find the generating function for the number of binary strings of length n with no two consecutive 1s; extract the first 6 terms and recognize the pattern
- Set up a transfer matrix for counting binary strings avoiding the substring '11'; compute the number of valid strings of length 4 and 5 by matrix powers
- Analyze the generating function (1 - x)^(-k) using partial fractions and singularity analysis; show that its coefficients grow like n^(k-1)
Next up: This stage equips you with the machinery to count complex combinatorial structures systematically; the next stage will apply these generating function techniques to specific families (partitions, trees, graphs) and introduce more advanced asymptotic methods for analyzing their behavior.
The definitive short course on generating functions; its conversational style and worked examples make abstract power-series methods feel concrete and immediately usable.
Bridges discrete mathematics and analysis, deepening fluency with sums, recurrences, and generating functions through a problem-driven approach that builds algebraic stamina.
Advanced Counting & Combinatorial Structures
ExpertDevelop expertise in Pólya enumeration, Möbius inversion, partition theory, and the interplay between combinatorics and algebra.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day (Erickson: 2–3 weeks; Stanley: 5–7 weeks)
- Pólya enumeration theorem: using group actions and cycle index polynomials to count distinct objects under symmetry
- Möbius inversion on posets: inverting functions via the Möbius function and its applications to combinatorial structures
- Partition theory: integer partitions, partition functions, generating functions, and asymptotic analysis
- Generating functions as a unifying tool: ordinary and exponential generating functions for solving recurrences and counting problems
- Symmetric functions and their role in enumerative combinatorics, including elementary and complete homogeneous symmetric functions
- Poset theory fundamentals: partially ordered sets, lattices, and their combinatorial significance
- The interplay between algebra and combinatorics: how algebraic structures illuminate counting problems
- Asymptotic methods and analytic combinatorics: estimating growth rates of combinatorial sequences
- How does the cycle index polynomial encode symmetries, and how do you use it to count distinct colorings or arrangements under group actions?
- What is the Möbius function on a poset, and how does Möbius inversion allow you to recover a function from its cumulative sums?
- Explain the connection between integer partitions and generating functions; how do you compute partition function values?
- How do ordinary and exponential generating functions differ, and when should you use each type to solve a combinatorial problem?
- What role do symmetric functions play in enumerative combinatorics, and how do they relate to partition theory?
- How can you apply Pólya enumeration to count necklaces or Burnside's lemma to count orbits under group actions?
- Work through Erickson's examples on Pólya enumeration: compute cycle index polynomials for small groups (cyclic, dihedral) and use them to count distinct necklaces or bracelets with k colors
- Solve 5–8 Möbius inversion problems from Stanley (Vol. 1): invert functions on the divisibility poset, subset lattice, and other natural posets; verify your results
- Generate the first 20–30 partition numbers using the recurrence relation and generating function approach; compare computational methods
- Derive and manipulate generating functions for at least 3 non-trivial combinatorial sequences (e.g., Catalan numbers, Fibonacci variants, restricted partitions); extract coefficients and verify against direct counts
- Prove or verify 2–3 identities involving symmetric functions (e.g., Newton's identities, Schur function properties) and relate them to partition enumeration
- Apply Burnside's lemma and Pólya enumeration to count distinct structures under symmetry (e.g., colorings of a cube, graphs on labeled vertices up to isomorphism)
Next up: This stage equips you with powerful algebraic and analytic tools—Pólya enumeration, Möbius inversion, and generating functions—that form the foundation for specialized topics such as matroid theory, algebraic combinatorics, and applications to graph enumeration and design theory in subsequent stages.
Provides a clean treatment of Pólya theory and Möbius inversion that bridges the gap between intermediate enumeration and the algebraic methods needed for the next books.
The canonical graduate reference for enumeration; its treatment of posets, Möbius functions, and generating functions is unmatched in depth and precision.
Graph Theory & Extremal Combinatorics
ExpertUnderstand how combinatorial counting interacts with graph theory, probabilistic arguments, and extremal problems — the frontier of modern combinatorics.
▸ Study plan for this stage
Pace: 12–14 weeks, ~40–50 pages/day (Diestel: 6–7 weeks, ~35 pages/day; Alon: 6–7 weeks, ~45 pages/day)
- Graph connectivity, planarity, and coloring: foundational structures and their extremal properties
- Matching theory and network flows: how optimization problems encode combinatorial constraints
- Ramsey theory and Turán-type problems: quantifying unavoidable structures in large graphs
- The probabilistic method: using randomness to prove existence of combinatorial objects without explicit construction
- Linearity of expectation and concentration inequalities: tools for analyzing random variables in graph settings
- Lovász Local Lemma: resolving dependencies in probabilistic arguments for dense constraint systems
- Applications of probabilistic methods to graph coloring, independent sets, and extremal graph theory
- What is the relationship between graph connectivity and minimum vertex cuts, and how do Menger's theorem and max-flow min-cut duality formalize this?
- How does Turán's theorem characterize the densest triangle-free graph, and what does this reveal about extremal problems more broadly?
- Explain the probabilistic method: how can you prove a combinatorial object exists without constructing it explicitly?
- What is the Lovász Local Lemma, and why is it powerful for problems where events have limited dependencies?
- How do concentration inequalities (Chebyshev, Chernoff bounds) allow you to move from expected values to high-probability guarantees?
- Describe a concrete application where the probabilistic method yields a better bound than a greedy or algebraic approach
- Work through Diestel's exercises on connectivity (Ch. 3): prove that a 2-connected graph has a cycle through any two vertices; apply Menger's theorem to specific graph families
- Solve extremal problems from Diestel (Ch. 7): compute the Turán number ex(n, K_r) for small r; verify the extremal graph is the Turán graph T(n,r)
- Implement a max-flow algorithm (Ford–Fulkerson or similar) on a concrete network; verify it matches the min-cut bound
- Prove a non-constructive existence result using linearity of expectation: e.g., show a graph with high chromatic number and high girth exists without building it
- Apply the Lovász Local Lemma to a constraint satisfaction problem (e.g., hypergraph coloring or satisfiability); verify the dependency condition and compute the probability bound
- Reproduce a probabilistic proof from Alon (e.g., Ramsey numbers, independent set in regular graphs); identify where linearity of expectation or concentration is used
- Design a randomized algorithm for a graph problem (e.g., MAX-CUT, vertex cover); analyze its expected approximation ratio using concentration inequalities
Next up: This stage equips you with both the structural language of graphs and the probabilistic toolkit to tackle modern extremal and algorithmic problems, preparing you to explore applications in complexity theory, random graph models, or specialized topics like additive combinatorics where these tools are essential.
The standard graduate graph theory text; its rigorous treatment of matchings, flows, and Ramsey theory provides the structural counterpart to the enumerative techniques already learned.
Introduces probabilistic and algebraic tools for extremal combinatorics, completing the picture of how counting arguments power the deepest results in the field.
Discussion
Keep reading
Paths that share books, cover the same subject, or open a related topic.
