Combinatorics
Combinatorics
£52.00
GBPCombinatorics is mathematics of enumeration, existence, construction, and optimization questions concerning finite sets. This text focuses on the first three types of questions and covers basic counting and existence principles, distributions, generating functions, recurrence relations, Pólya theory, combinatorial designs, error correcting codes, partially ordered sets, and selected applications to graph theory including the enumeration of trees, the chromatic polynomial, and introductory Ramsey theory. The only prerequisites are single-variable calculus and familiarity with sets and basic proof techniques. It is flexible enough to be used for undergraduate courses in combinatorics, second courses in discrete mathematics, introductory graduate courses in applied mathematics programs, as well as for independent study or reading courses. It also features approximately 350 reading questions spread throughout its eight chapters. These questions provide checkpoints for learning and prepare the reader for the end-of-section exercises of which there are over 470.
- Flexible enough to be used for undergraduate courses in combinatorics, second courses in discrete mathematics, introductory graduate courses in applied mathematics programs, as well as for independent study or reading courses
- 350 reading questions are spread through the chapters, providing checkpoints for learning to prepare the reader for the end-of-section exercises
- Travel notes enrich the material of each section with anecdotes, open problems, suggestions for further reading and biographical information about mathematicians involved in the discoveries
Product details
March 2010Hardback
9780883857625
410 pages
261 × 182 × 26 mm
0.87kg
51 b/w illus.
Temporarily unavailable - available from TBC
Table of Contents
- Preface
- Before you go
- Notation
- Part I. Principles of Combinatorics:
- 1. Typical counting questions, the product principle
- 2. Counting, overcounting, the sum principle
- 3. Functions and the bijection principle
- 4. Relations and the equivalence principle
- 5. Existence and the pigeonhole principle
- Part II. Distributions and Combinatorial Proofs:
- 6. Counting functions
- 7. Counting subsets and multisets
- 8. Counting set partitions
- 9. Counting integer partitions
- Part III. Algebraic Tools:
- 10. Inclusion-exclusion
- 11. Mathematical induction
- 12. Using generating functions, part I
- 13. Using generating functions, part II
- 14. techniques for solving recurrence relations
- 15. Solving linear recurrence relations
- Part IV. Famous Number Families:
- 16. Binomial and multinomial coefficients
- 17. Fibonacci and Lucas numbers
- 18. Stirling numbers
- 19. Integer partition numbers
- Part V. Counting Under Equivalence:
- 20. Two examples
- 21. Permutation groups
- 22. Orbits and fixed point sets
- 23. Using the CFB theorem
- 24. Proving the CFB theorem
- 25. The cycle index and Pólya's theorem
- Part VI. Combinatorics on Graphs:
- 26. Basic graph theory
- 27. Counting trees
- 28. Colouring and the chromatic polynomial
- 29. Ramsey theory
- Part VII. Designs and Codes:
- 30. Construction methods for designs
- 31. The incidence matrix, symmetric designs
- 32. Fisher's inequality, Steiner systems
- 33. Perfect binary codes
- 34. Codes from designs, designs from codes
- Part VIII. Partially Ordered Sets:
- 35. Poset examples and vocabulary
- 36. Isomorphism and Sperner's theorem
- 37. Dilworth's theorem
- 38. Dimension
- 39. Möbius inversion, part I
- 40. Möbius inversion, part II
- Bibliography
- Hints and answers to selected exercises.
