You are previewing Combinatorics.
O'Reilly logo
Combinatorics

Book Description

Combinatorics is a subject of increasing importance, owing to its links with computer science, statistics and algebra. This is a textbook aimed at second-year undergraduates to beginning graduates. It stresses common techniques (such as generating functions and recursive construction) which underlie the great variety of subject matter and also stresses the fact that a constructive or algorithmic proof is more valuable than an existence proof. The book is divided into two parts, the second at a higher level and with a wider range than the first. Historical notes are included which give a wider perspective on the subject. More advanced topics are given as projects and there are a number of exercises, some with solutions given.

Table of Contents

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