Combinatorics

A book in 20 chapters about counting, arranging and connecting: from "how many ways?" to graphs, Ramsey theory, the probabilistic method and the codes that carried pictures home from Mars. Each chapter starts from a question, proves what it claims, works examples step by step, and ends with questions whose answers are folded underneath.

How to read it

• In order. Each chapter needs only the ones before it; the Next link at the end of every chapter walks you through.
• Levels inside a chapter. The box at the top of each chapter says which sections are beginner, intermediate, advanced or expert. On a first read, skip the harder sections and come back later.
• Slower help. The first chapters point to the matching lessons on the Topics shelf, which teach the same ideas more gently, for younger readers.
• Check by listing. For small cases, write every arrangement out, or let a few lines of Python do it; most chapters show how.

Contents

Part	Chapter	Level
I. Counting	1. Counting principles	beginner
	2. Permutations and combinations	beginner
	3. Binomial coefficients	beginner to intermediate
	4. The pigeonhole principle	beginner to intermediate
II. Techniques	5. Inclusion-exclusion	intermediate
	6. Recurrences	intermediate
	7. Generating functions	intermediate to advanced
	8. Catalan numbers and lattice paths	intermediate
	9. Stirling numbers and partitions	intermediate to advanced
III. Graphs	10. Graphs	intermediate
	11. Trees	intermediate
	12. Planar graphs and colouring	intermediate to advanced
	13. Matchings and flows	advanced
	14. Hamiltonian cycles and hard problems	advanced
IV. Advanced combinatorics	15. Counting with symmetry	advanced
	16. Ramsey theory	advanced
	17. The probabilistic method	advanced to expert
	18. Extremal combinatorics	advanced to expert
	19. Designs and codes	advanced
V. The frontier	20. Where combinatorics goes	expert

The glossary defines every term, with a link to the chapter that teaches it.

Three ways in

• Starting out: read chapters 1 to 5. They are the counting every later chapter uses.
• For computing and puzzles: chapters 6 to 8, then the graphs of chapters 10 to 14.
• You know some algebra and probability: read chapters 15 to 20. The Algebra book's group chapters and the Number theory book's partitions chapter are the companions.