The original goal of writing this book was to introduce the reader to the tools of combinatorics from an applied point of view. This third edition of Applied Combinatorics was substantially rewritten. There are many new examples and exercises. References throughout the book to modern literature and real applications, a key feature of the book, have been updated and expanded. The exposition continues to be updated with each new edition, as the first edition was published 40 years ago.
The emphasis on applications from computer science, genetics, experimental design, chemistry, scheduling, voting, and other topics remains a central feature of the book. Unique to the literature is that entire sections focus on applications such as switching functions, the use of enzymes to uncover unknown RNA chains, searching and sorting problems of information retrieval, construction of error-correcting codes, counting of chemical compounds, calculation of power in voting situations, and uses of Fibonacci numbers. There are entire sections on applications of recurrences involving convolutions, applications of eulerian chains, and applications of generating functions.
The book continues to be based on the authors’ philosophy that the best way to learn mathematics is through problem solving. Combinatorics can be a wonderful mechanism for introducing students to proofs. However, the book is not designed for an introduction to proofs course. The authors treat proofs as rather informal, and many of the harder proofs in the book are optional.
Applied Combinatorics, Third Edition is divided into four parts. The first part introduces the basic tools of combinatorics and their applications. The remaining three parts are organized around the three basic problems of combinatorics: the counting problem, the existence problem, and the optimization problem.
Most of the book is written for a first course on the topic at the undergraduate level. On the other hand, at a fast pace, there is more than enough material for a challenging graduate course. This book first appeared when courses on combinatorics were rare. We are pleased to think that, through its use, the book has helped to establish a key course in many colleges and universities throughout the world. We hope that this new edition will remain a valuable tool for instructors and students alike.
Chapter 1: What Is Combinatorics? THE BASIC TOOLS OF COMBINATORICS
Chapter 2: Basic Counting Rules;
Chapter 3: Introduction to Graph Theory;
Chapter 4 Relations; THE COUNTING PROBLEM
Chapter 5: Generating Functions and Their Applications;
Chapter 6: Recurrence Relations;
Chapter 7: The Principle of Inclusion and Exclusion;
Chapter 8: The Pólya Theory of Counting; THE EXISTENCE PROBLEM
Chapter 9: Combinatorial Designs;
Chapter 10: Coding Theory;
Chapter 11: Existence Problems in Graph Theory; COMBINATORIAL OPTIMIZATION
Chapter 12: Matching and Covering;
Chapter 13: Optimization Problems for Graphs and Networks; Appendix: Answers to Selected Exercises; Author Index; Subject Index; References appear at the end of each chapter.
Biography
Fred S. Roberts is professor of mathematics and director of DIMACS at Rutgers University.
Barry Tesman is a professor of mathematics at Dickinson College.
