Table of Contents
About the Authors
Preface to 2016 Edition
1. An Introduction to Combinatorics
2. Strings, Sets and Binomial Coefficients
4. Combinatorial Basics
5. Graph Theory
6. Partially Ordered Sets
8. Generating Functions
9. Recurrence Equations
11. Applying Probability to Combinatorics
12. Graph Algorithms
13. Network Flows
14. Combinatorial Applications of Network Flows
15. Polya’s Enumeration Theorem
16. The Many Faces of Combinatorics
B. Background Material for Combinatorics
C. List of Notation
About the Book
Applied Combinatorics is an open-source textbook for a course covering the fundamental enumeration techniques (permutations, combinations, subsets, pigeon hole principle), recursion and mathematical induction, more advanced enumeration techniques (inclusion-exclusion, generating functions, recurrence relations, Polyá theory), discrete structures (graphs, digraphs, posets, interval orders), and discrete optimization (minimum weight spanning trees, shortest paths, network flows). There are also chapters introducing discrete probability, Ramsey theory, combinatorial applications of network flows, and a few other nuggets of discrete mathematics.
About the Contributors
Mitchel T. Keller is an assistant professor in the Department of Mathematics at Washington and Lee University, a small liberal arts college in Lexington, Virginia. He holds a B.S. in mathematics from North Dakota State University and a Ph.D. in mathematics from the Georgia Institute of Technology. (His Ph.D. advisor is now his co-author on this book.) Mitch’s research interests are in the combinatorics of partially ordered sets, online algorithms, and combinatorial approaches to Stanley depth of monomial ideals. He likes to travel, bake, and take photographs. (The cover image for the 2016 Edition of Applied Combinatorics is of work his honors thesis student Matthew R. Kiser did on the board in Mitch’s office.) Mitch is also the Managing Director of the Mathematics Genealogy Project.
William T. Trotter is a professor in the School of Mathematics at the Georgia Institute of Technology in Atlanta. In a career spanning more than four decades, Tom has been a faculty member and administrator at the University of South Carolina, Arizona State University, and Georgia Tech. He has published extensively on the combinatorics of partially ordered sets, graph theory, Ramsey theory, and extremal combinatorics. His monograph on dimension theory for partially ordered sets has been in print for nearly 25 years. Tom is an avid movie buff, fan of the New York Yankees, and golfer.