Free

Combinatorics

By Unknown

Free

Read Now

Description Table of Contents Reviews Comments

Book Description

Table of Contents

Chapter 1. What is Combinatorics?
- 1A. Enumeration
- 1B. Graph Theory
- 1C. Ramsey Theory
- 1D. Design Theory
- 1E. Coding Theory
- Summary
Part I. Enumeration
- Chapter 2. Basic Counting Techniques
  - 2A. The product rule
  - 2B. The sum rule
  - 2C. Putting them together
  - 2D. Summing up
  - Summary
- Chapter 3. Permutations, Combinations, and the Binomial Theorem
  - 3A. Permutations
  - 3B. Combinations
  - 3C. The Binomial Theorem
  - Summary
- Chapter 4. Bijections and Combinatorial Proofs
  - 4A. Counting via bijections
  - 4B. Combinatorial proofs
  - Summary
- Chapter 5. Counting with Repetitions
  - 5A. Unlimited repetition
  - 5B. Sorting a set that contains repetition
  - Summary
- Chapter 6. Induction and Recursion
  - 6A. Recursively-defined sequences
  - 6B. Basic induction
  - 6C. More advanced induction
  - Summary
- Chapter 7. Generating Functions
  - 7A. What is a generating function?
  - 7B. The Generalised Binomial Theorem
  - 7C. Using generating functions to count things
  - Summary
- Chapter 8. Generating Functions and Recursion
  - 8A. Partial fractions
  - 8B. Factoring polynomials
  - 8C. Using generating functions to solve recursively-defined sequences
  - Summary
- Chapter 9. Some Important Recursively-Defined Sequences
  - 9A. Derangements
  - 9B. Catalan numbers
  - 9C. Bell numbers and exponential generating functions
  - Summary
- Chapter 10. Other Basic Counting Techniques
  - 10A. The Pigeonhole Principle
  - 10B. Inclusion-Exclusion
  - Summary
Part II. Graph Theory
- Chapter 11. Basics of Graph Theory
  - 11A. Background
  - 11B. Basic definitions, terminology, and notation
  - 11C. Deletion, complete graphs, and the Handshaking Lemma
  - 11D. Graph isomorphisms
  - Summary
- Chapter 12. Moving through graphs
  - 12A. Directed graphs
  - 12B. Walks and connectedness
  - 12C. Paths and cycles
  - 12D. Trees
  - Summary
- Chapter 13. Euler and Hamilton
  - 13A. Euler tours and trails
  - 13B. Hamilton paths and cycles
  - Summary
- Chapter 14. Graph Colouring
  - 14A. Edge colouring
  - 14B. Ramsey Theory
  - 14C. Vertex colouring
  - Summary
- Chapter 15. Planar graphs
  - 15A. Planar graphs
  - 15B. Euler's Formula
  - 15C. Map colouring
  - Summary
Part III. Design Theory
- Chapter 16. Latin squares
  - 16A. Latin squares and Sudokus
  - 16B. Mutually orthogonal Latin squares (MOLS)
  - 16C. Systems of distinct representatives
  - Summary
- Chapter 17. Designs
  - 17A. Balanced Incomplete Block Designs (BIBD)
  - 17B. Constructing designs, and existence of designs
  - 17C. Fisher's Inequality
  - Summary
- Chapter 18. More designs
  - 18A. Steiner and Kirkman triple systems
  - 18B. t-designs
  - 18C. Affine planes
  - 18D. Projective planes
  - Summary
- Chapter 19. Designs and Codes
  - 19A. Introduction
  - 19B. Error-correcting codes
  - 19C. Using the generator matrix for encoding
  - 19D. Using the parity-check matrix for decoding
  - 19E. Codes from designs
  - Summary
- Index
- List of Notation
- Appendix A. Solutions to selected exercises