The original goal in 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 exercises. Additionally, references throughout the book have been updated both in terms of new editions of previously referenced works, as well as with references to recently published books and articles. As the first edition appeared decades prior, the diction in the exposition has been updated and is more contemporary.
The book continues to be based on the authors’ philosophy the best way to learn mathematics is through problem solving. Combinatorics can be a wonderful mechanism for introducing students to proofs. The authors treat proofs as rather informal while many of the harder proofs in the book are optional.
In this new edition, many new examples and exercises appear, as well as an overall updating of the exposition for more contemporary diction.
The book is divided into four parts.The first part introduces the basic tools of combinatorics and their applications. The remaining three parts are organizedaroundthe three basic problems of combinatorics: thecountingproblem,theexistenceproblem,andtheoptimizationproblem.Then Part IV ends with a discussion of optimizationproblemsforgraphsandnetworks.
Entire sections focus on applications 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.
Most of the book is written for a first course on the topic at the undergraduate level. 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. It is one of the classics that, through its use, helped to establish a viable course in many mathematics departments throughout the world. It remains a useful 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 Professor of Mathematics at Dickinson College.
