| |
| |
| Preface | |
| |
| |
| |
| What is Combinatorics? | |
| |
| |
| Sample problems | |
| |
| |
| How to use this book | |
| |
| |
| What you need to know | |
| |
| |
| Exercises | |
| |
| |
| |
| On numbers and counting | |
| |
| |
| 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 | |
| |
| |
| 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 | |
| |
| |
| 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 | |
| |
| |
| PIE | |
| |
| |
| A generalisation | |
| |
| |
| Stirling numbers | |
| |
| |
| Project: Stirling numbers and exponentials | |
| |
| |
| Even and odd permutations | |
| |
| |
| Exercises | |
| |
| |
| |
| Latin squares and SDRs | |
| |
| |
| Latin squares | |
| |
| |
| Systems of distinct representatives | |
| |
| |
| How many Latin squares? | |
| |
| |
| Quasigroups | |
| |
| |
| Project: Quasigroups and groups | |
| |
| |
| Orthogonal Latin squares | |
| |
| |
| Exercises | |
| |
| |
| |
| Extremal set theory | |
| |
| |
| Intersecting families | |
| |
| |
| Sperner families | |
| |
| |
| The De Bruijn-Erdos Theorem | |
| |
| |
| Project: Regular families | |
| |
| |
| Exercises | |
| |
| |
| |
| Steiner triple systems | |
| |
| |
| 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 | |
| |
| |
| 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 | |
| |
| |
| The Pigeonhole Principle | |
| |
| |
| Some special cases | |
| |
| |
| Ramsey's Theorem | |
| |
| |
| Bounds for Ramsey numbers | |
| |
| |
| Applications | |
| |
| |
| The infinite version | |
| |
| |
| Exercises | |
| |
| |
| |
| Graphs | |
| |
| |
| 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 | |
| |
| |
| 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 | |
| |
| |
| Partitions, diagrams and conjugacy classes | |
| |
| |
| Euler's Pentagonal Numbers Theorem | |
| |
| |
| Project: Jacobi's Identity | |
| |
| |
| Tableaux | |
| |
| |
| Symmetric polynomials | |
| |
| |
| Exercises | |
| |
| |
| |
| Automorphism groups and permutation groups | |
| |
| |
| 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 | |
| |
| |
| The Orbit-counting Lemma | |
| |
| |
| An application | |
| |
| |
| Cycle index | |
| |
| |
| Examples | |
| |
| |
| Direct and wreath products | |
| |
| |
| Stirling numbers revisited | |
| |
| |
| Project: Cycle index and symmetric functions | |
| |
| |
| Exercises | |
| |
| |
| |
| Designs | |
| |
| |
| 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 | |
| |
| |
| Finding out a liar | |
| |
| |
| Definitions | |
| |
| |
| Probabilistic considerations | |
| |
| |
| Some bounds | |
| |
| |
| Linear codes; Hamming codes | |
| |
| |
| Perfect codes | |
| |
| |
| Linear codes and projective spaces | |
| |
| |
| Exercises | |
| |
| |
| |
| Graph colourings | |
| |
| |
| More on bipartite graphs | |
| |
| |
| Vertex colourings | |
| |
| |
| Project: Brooks' Theorem | |
| |
| |
| Perfect graphs | |
| |
| |
| Edge colourings | |
| |
| |
| Topological graph theory | |
| |
| |
| Project: The Five-colour Theorem | |
| |
| |
| Exercises | |
| |
| |
| |
| The infinite | |
| |
| |
| 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? | |
| |
| |
| Computational complexity | |
| |
| |
| Some graph-theoretic topics | |
| |
| |
| Computer software | |
| |
| |
| Unsolved problems | |
| |
| |
| Further reading | |
| |
| |
| Answers to selected exercises | |
| |
| |
| Bibliography | |
| |
| |
| Index | |