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.
The text emphasizes the brands of thinking that are characteristic of combinatorics: bijective and combinatorial proofs, recursive analysis, and counting problem classification. 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.
Before You Go
1. Principles of Combinatorics
2. Distributions and Combinatorial Proofs
3. Algebraic Tools
4. Famous Number Families
5. Counting Under Equivalence
6. Combinatorics on Graphs
7. Designs and Codes
8. Partially Ordered Sets
Hints and Answers to Selected Exercises
List of Notation
A university has 120 incoming freshman that still have to be assigned to on-campus housing. The only remaining dorm holds 105 students and contains 42 doubles (rooms housing two students) and seven triples (three students). In how many ways can the university select 105 students to house in this dorm and then arrange those students into roommate pairs and triples, without yet assigning them to rooms?
In the previous exercise, suppose the university gets approval to house temporarily the remaining 15 students among the dorm's three lounges. Each lounge will house five students. How many ways are there for the university to assign all 120 students to rooms?
David R. Mazur (Western New England College, in Springfield, Mass.), who received his Ph.D. in mathematics from Johns Hopkins University in 1999, was a 2000-2001 Project NExT fellow. Mazur (email@example.com) now serves the MAA as a consultant to Project NExT and as a member of its Membership Committee. This is Mazur's first book. He will be doing his first book signing at the Joint Mathematics Meetings in San Francisco in January 2010.
Combinatorics: A Guided Tour is an undergraduate textbook designed for a first course or reading course in combinatorics. A student learning from this book should have taken one year of calculus and an introduction to proofs. The book takes a more theoretical approach in presenting combinatorics, in contrast to some of the more application-based combinatorics books on the market.