Mazur D.R. Combinatorics: A Guided Tour

The Mathematical Association of America, 2009. — 391 pages. — (MAA Textbooks)
ISBN: 0883857626 ISBN13: 9780883857625This book provides a journey through introductory combinatorics that the reader can undertake
during one semester, two quarters, or in a independent study or self-study setting. It is not intended to be encyclopedic. Rather, it surveys a good cross-section of combinatorics as it has developed within the last century with an eye towards its characteristic brand of thinking, its interconnections with other mathematical fields, and some of its applications. Combinatorics can rightly be called the mathematics of counting. More specifically, it is the mathematics of the enumeration, existence, construction, and optimization questions concerning finite sets.
Here are some brief illustrations.Enumeration: How many? How many different 9x9 Sudoku boards are there? This number has been computed exactly and it is astronomical—about 6.6 sextillion. Determining this number by simply listing every possible board is not a viable approach. Combinatorics involves mathematical techniques for determining the answer to a counting question without listing the objects being counted.
Existence: Is it possible? Take any 25 people living on the earth. Among the members of this group will you always be able to find four people who all know each other or else five people who all don’t know each other? Yes: this is guaranteed no matter what group of 25 you choose. Despite its innocent-sounding nature, this question wasn’t answered until 1993 and required careful combinatorial analysis as well as thousands of hours of computer time.
Construction: Can it be built? The Mariner 9 spacecraft orbited Mars in 1971-72 and sent back photographs that gave a complete picture of the planet’s surface. Your CD player can play a disc flawlessly despite occasional scratches on the disc’s surface. Both of these applications involve error-correcting codes that transmit information with 100% accuracy despite occasional errors in transmission. Construction methods for many error-correcting codes use combinatorics.
Optimization: What is the best way? Your car’s GPS navigation system quickly finds the fastest route from point A to point B. It essentially solves instances of a combinatorial optimization problem called the shortest path problem, which is but one of a broad class of network optimization problems that have widespread modern application.In this book we consider enumeration, existence, and construction questions.