| Preface | |
| What is Combinatorics? | p. 1 |
| Sample problems | |
| How to use this book | |
| What you need to know | |
| Exercises | |
| On numbers and counting | p. 7 |
| Natural numbers and arithmetic | |
| Induction | |
| Some useful functions | |
| Orders of magnitude | |
| Different ways of counting | |
| Double counting | |
| Appendix on set notation | |
| Exercises | |
| Subsets, partitions, permutations | p. 21 |
| Subsets | |
| Subsets of fixed size | |
| The Binomial Theorem and Pascal's Triangle | |
| Project: Congruences of binomial coefficients | |
| Permutations | |
| Estimates for factorials | |
| Selections | |
| Equivalence and order | |
| Project: Finite topologies | |
| Project: Cayley's Theorem on trees | |
| Bell numbers | |
| Generating combinatorial objects | |
| Exercises | |
| Recurrence relations and generating functions | p. 49 |
| Fibonacci numbers | |
| Aside on formal power series | |
| Linear recurrence relations with constant coefficients | |
| Derangements and involutions | |
| Catalan and Bell numbers | |
| Computing solutions to recurrence relations | |
| Project: Finite fields and QUICKSORT | |
| Exercises | |
| The Principle of Inclusion and Exclusion | p. 75 |
| PIE | |
| A generalisation | |
| Stirling numbers | |
| Project: Stirling numbers and exponentials | |
| Even and odd permutations | |
| Exercises | |
| Latin squares and SDRs | p. 87 |
| Latin squares | |
| Systems of distinct representatives | |
| How many Latin squares? | |
| Quasigroups | |
| Project: Quasigroups and groups | |
| Orthogonal Latin squares | |
| Exercises | |
| Extremal set theory | p. 99 |
| Intersecting families | |
| Sperner families | |
| The De Bruijn-Erdos Theorem | |
| Project: Regular families | |
| Exercises | |
| Steiner triple systems | p. 107 |
| Steiner systems | |
| A direct construction | |
| A recursive construction | |
| Packing and covering | |
| Project: Some special Steiner triple systems | |
| Project: Tournaments and Kirkman's schoolgirls | |
| Exercises | |
| Finite geometry | p. 123 |
| Linear algebra over finite fields | |
| Gaussian coefficients | |
| Projective geometry | |
| Axioms for projective geometry | |
| Projective planes | |
| Other kinds of geometry | |
| Project: Coordinates and configurations | |
| Project: Proof of the Bruck-Ryser Theorem | |
| Finite fields | |
| Exercises | |
| Ramsey's Theorem | p. 147 |
| The Pigeonhole Principle | |
| Some special cases | |
| Ramsey's Theorem | |
| Bounds for Ramsey numbers | |
| Applications | |
| The infinite version | |
| Exercises | |
| Graphs | p. 159 |
| Definitions | |
| Trees and forests | |
| Minimal spanning trees | |
| Eulerian graphs | |
| Hamiltonian graphs | |
| Project: Gray codes | |
| The Travelling Salesman | |
| Digraphs | |
| Networks | |
| Menger, Konig and Hall | |
| Diameter and girth | |
| Project: Moore graphs | |
| Exercises | |
| Posets, lattices and matroids | p. 187 |
| Posets and lattices | |
| Linear extensions of a poset | |
| Distributive lattices | |
| Aside on propositional logic | |
| Chains and antichains | |
| Products and dimension | |
| The Mobius function of a poset | |
| Matroids | |
| Project: Arrow's Theorem | |
| Exercises | |
| More on partitions and permutations | p. 209 |
| Partitions, diagrams and conjugacy classes | |
| Euler's Pentagonal Numbers Theorem | |
| Project: Jacobi's Identity | |
| Tableaux | |
| Symmetric polynomials | |
| Exercises | |
| Automorphism groups and permutation groups | p. 225 |
| Three definitions of a group | |
| Examples of groups | |
| Orbits and transitivity | |
| The Schreier-Sims algorithm | |
| Primitivity and multiple transitivity | |
| Examples | |
| Project: Cayley digraphs and Frucht's Theorem | |
| Exercises | |
| Enumeration under group action | p. 245 |
| The Orbit-counting Lemma | |
| An application | |
| Cycle index | |
| Examples | |
| Direct and wreath products | |
| Stirling numbers revisited | |
| Project: Cycle index and symmetric functions | |
| Exercises | |
| Designs | p. 257 |
| Definitions and examples | |
| To repeat or not to repeat | |
| Fisher's Inequality | |
| Designs from finite geometry | |
| Small designs | |
| Project: Hadamard matrices | |
| Exercises | |
| Error-correcting codes | p. 271 |
| Finding out a liar | |
| Definitions | |
| Probabilistic considerations | |
| Some bounds | |
| Linear codes; Hamming codes | |
| Perfect codes | |
| Linear codes and projective spaces | |
| Exercises | |
| Graph colourings | p. 291 |
| More on bipartite graphs | |
| Vertex colourings | |
| Project: Brooks' Theorem | |
| Perfect graphs | |
| Edge colourings | |
| Topological graph theory | |
| Project: The Five-colour Theorem | |
| Exercises | |
| The infinite | p. 307 |
| Counting infinite sets | |
| Konig's Infinity Lemma | |
| Posets and Zorn's Lemma | |
| Ramsey theory | |
| Systems of distinct representatives | |
| Free constructions | |
| The random graph | |
| Exercises | |
| Where to from here? | p. 325 |
| Computational complexity | |
| Some graph-theoretic topics | |
| Computer software | |
| Unsolved problems | |
| Further reading | |
| Answers to selected exercises | p. 339 |
| Bibliography | p. 343 |
| Index | p. 347 |
| Table of Contents provided by Syndetics. All Rights Reserved. |
