Combinatorics : a guided tour
Author(s)
Bibliographic Information
Combinatorics : a guided tour
（MAA textbooks）
Mathematical Association of America, c2010
Available at / 6 libraries
-
No Libraries matched.
- Remove all filters.
Note
Includes bibliographical references (p. 365-367) and index
Description and Table of Contents
Description
Combinatorics 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, Polya 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.
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 Polya'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. Moebius inversion, part I
- 40. Moebius inversion, part II
- Bibliography
- Hints and answers to selected exercises.
by "Nielsen BookData"
