Applied Combinatorics

The new 6th edition of Applied Combinatorics builds on the previous editions with more in depth analysis of computer systems in order to help develop proficiency in basic discrete math problem solving. As one of the most widely used book in combinatorial problems, this edition explains how to reason and model combinatorically while stressing the systematic analysis of different possibilities, exploration of the logical structure of a problem, and ingenuity. Although important uses of combinatorics in computer science, operations research, and finite probability are mentioned, these applications are often used solely for motivation. Numerical examples involving the same concepts use more interesting settings such as poker probabilities or logical games. This book is designed for use by students with a wide range of ability and maturity (sophomores through beginning graduate students). The stronger the students, the harder the exercises that can be assigned. The book can be used for one-quarter, two-quarter, or one-semester course depending on how much material is used.

Table of Contents:
Prelude xi Part One Graph Theory 1 Chapter 1 Elements of Graph Theory 3 1.1 Graph Models 3 1.2 Isomorphism 14 1.3 Edge Counting 24 1.4 Planar Graphs 31 1.5 Summary and References 44 Supplementary Exercises 45 Chapter 2 Covering Circuits and Graph Coloring 49 2.1 Euler Cycles 49 2.2 Hamilton Circuits 56 2.3 Graph Coloring 68 2.4 Coloring Theorems 77 2.5 Summary and References 86 Supplement: Graph Model for Instant Insanity 87 Supplement Exercises 92 Chapter 3 Trees and Searching 93 3.1 Properties of Trees 93 3.2 Search Trees and Spanning Trees 103 3.3 The Traveling Salesperson Problem 113 3.4 Tree Analysis of Sorting Algorithms 121 3.5 Summary and References 125 Chapter 4 Network Algorithms 127 4.1 Shortest Paths 127 4.2 Minimum Spanning Trees 131 4.3 Network Flows 135 4.4 Algorithmic Matching 153 4.5 The Transportation Problem 164 4.6 Summary and References 174 Part Two Enumeration 177 Chapter 5 General Counting Methods for Arrangements and Selections 179 5.1 Two Basic Counting Principles 179 5.2 Simple Arrangements and Selections 189 5.3 Arrangements and Selections with Repetitions 206 5.4 Distributions 214 5.5 Binomial Identities 226 5.6 Summary and References 236 Supplement: Selected Solutions to Problems in Chapter 5 237 Chapter 6 Generating Functions 249 6.1 Generating Function Models 249 6.2 Calculating Coefficients of Generating Functions 256 6.3 Partitions 266 6.4 Exponential Generating Functions 271 6.5 A Summation Method 277 6.6 Summary and References 281 Chapter 7 Recurrence Relations 283 7.1 Recurrence Relation Models 283 7.2 Divide-and-Conquer Relations 296 7.3 Solution of Linear Recurrence Relations 300 7.4 Solution of Inhomogeneous Recurrence Relations 304 7.5 Solutions with Generating Functions 308 7.6 Summary and References 316 Chapter 8 Inclusion–Exclusion 319 8.1 Counting with Venn Diagrams 319 8.2 Inclusion–Exclusion Formula 328 8.3 Restricted Positions and Rook Polynomials 340 8.4 Summary and Reference 351 Part Three Additional Topics 353 Chapter 9 Polya’s Enumeration Formula 355 9.1 Equivalence and Symmetry Groups 355 9.2 Burnside’s Theorem 363 9.3 The Cycle Index 369 9.4 Polya’s Formula 375 9.5 Summary and References 382 Chapter 10 Games with Graphs 385 10.1 Progressively Finite Games 385 10.2 Nim-Type Games 393 10.3 Summary and References 400 Postlude 401 Appendix 415 A.1 Set Theory 415 A.2 Mathematical Induction 420 A.3 A Little Probability 423 A.4 The Pigeonhole Principle 427 A.5 Computational Complexity and NP-Completeness 430 Glossary of Counting and Graph Theory Terms 435 Bibliography 439 Solutions To Odd-Numbered Problems 441 Index 475