Now with solutions to selected problems, Applied Combinatorics, Second Edition presents the tools of combinatorics from an applied point of view. This bestselling textbook offers numerous references to the literature of combinatorics and its applications that enable readers to delve more deeply into the topics.
After introducing fundamental counting rules and the tools of graph theory and relations, the authors focus on three basic problems of combinatorics: counting, existence, and optimization problems. They discuss advanced tools for dealing with the counting problem, including generating functions, recurrences, inclusion/exclusion, and Polya theory. The text then covers combinatorial design, coding theory, and special problems in graph theory. It also illustrates the basic ideas of combinatorial optimization through a study of graphs and networks.
Fred S. Roberts is Professor of Mathematics and Director of DIMACS at Rutgers University. Barry Tesman is Professor of Mathematics at Dickinson College.
What Is Combinatorics? The Three Problems of Combinatorics The History and Applications of Combinatorics THE BASIC TOOLS OF COMBINATORICS Basic Counting Rules The Product Rule The Sum Rule Permutations Complexity of Computation r-Permutations Subsets r-Combinations Probability Sampling with Replacement Occupancy Problems Multinomial Coefficients Complete Digest by Enzymes Permutations with Classes of Indistinguishable Objects Revisited The Binomial Expansion Power in Simple Games Generating Permutations and Combinations Inversion Distance between Permutations and the Study of Mutations Good Algorithms Pigeonhole Principle and Its Generalizations Introduction to Graph Theory Fundamental Concepts Connectedness Graph Coloring and Its Applications Chromatic Polynomials Trees Applications of Rooted Trees to Searching, Sorting, and Phylogeny Reconstruction Representing a Graph in the Computer Ramsey Numbers Revisited Relations Relations Order Relations and Their Variants Linear Extensions of Partial Orders Lattices and Boolean Algebras THE COUNTING PROBLEM Generating Functions and Their Applications Examples of Generating Functions Operating on Generating Functions Applications to Counting The Binomial Theorem Exponential Generating Functions and Generating Functions for Permutations Probability Generating Functions The Coleman and Banzhaf Power Indices Recurrence Relations Some Examples The Method of Characteristic Roots Solving Recurrences Using Generating Functions Some Recurrences Involving Convolutions The Principle of Inclusion and Exclusion The Principle and Some of Its Applications The Number of Objects Having Exactly m Properties The Polya Theory of Counting Equivalence Relations Permutation Groups Burnside's Lemma Distinct Colorings The Cycle Index Polya's Theorem THE EXISTENCE PROBLEM Combinatorial Designs Block Designs Latin Squares Finite Fields and Complete Orthogonal Families of Latin Squares Balanced Incomplete Block Designs Finite Projective Planes Coding Theory Information Transmission Encoding and Decoding Error-Correcting Codes Linear Codes The Use of Block Designs to Find Error-Correcting Codes Existence Problems in Graph Theory Depth-First Search: A Test for Connectedness The One-Way Street Problem Eulerian Chains and Paths Applications of Eulerian Chains and Paths Hamiltonian Chains and Paths Applications of Hamiltonian Chains and Paths COMBINATORIAL OPTIMIZATION Matching and Covering Some Matching Problems Some Existence Results: Bipartite Matching and Systems of Distinct Representatives The Existence of Perfect Matchings for Arbitrary Graphs Maximum Matchings and Minimum Coverings Finding a Maximum Matching Matching as Many Elements of X as Possible Maximum-Weight Matching Stable Matchings Optimization Problems for Graphs and Networks Minimum Spanning Trees The Shortest Route Problem Network Flows Minimum-Cost Flow Problems Appendix: Answers to Selected Exercises Author Index Subject Index References appear at the end of each chapter.