Combinatorics: A Guided Tour - David R. Mazur

Combinatorics: A Guided Tour

by David R. Mazur


# ISBN-13: 9780883857625
# Publisher: Mathematical Association of America
# Publication year: 2010
# Series: Mathematical Association of America Textbooks Series
# Pages: 410


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

Contents
========

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.


Author
======
David R. Mazur is Associate Professor of Mathematics at Western New England College in Springfield, Massachusetts. He was born on October 23, 1971 in Washington, D.C. He received his undergraduate degree in Mathematics from the University of Delaware in 1993, and also won the Department of Mathematical Sciences' William D. Clark prize for 'unusual ability' in the major that year. He then received two fellowships for doctoral study in the Department of Mathematical Sciences (now the Department of Applied Mathematics and Statistics) at The Johns Hopkins University. From there he received his Master's in 1996 and his Ph.D. in 1999 under the direction of Leslie A. Hall, focusing on operations research, integer programming, and polyhedral combinatorics. His dissertation, 'Integer Programming

-_-

If you liked the book, do please consider purchasing one. Thank you. :-)