| |
| |
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 | |