Applied Combinatorics

Title page......Page 1
Preface......Page 3
PART ONE GRAPH THEORY......Page 11
1.1 Graph Models......Page 13
1.2 Isomorphism......Page 29
1.3 Edge Counting......Page 38
1.4 Planar Graphs......Page 45
1.5 Summary and References......Page 58
Supplement I: Representing Graphs Inside a Computer......Page 59
Supplement II: Supplementary Exercises......Page 61
2.1 Euler Circuits......Page 67
2.2 Hamilton Circuits......Page 75
2.3 Graph Coloring......Page 86
2.4 Coloring Theorems......Page 95
2.5 Summary and References......Page 101
3.1 Properties of Trees......Page 103
3.2 Depth-First and Breadth-First Search......Page 113
3.3 Spanning Trees......Page 120
3.4 The Traveling Salesperson Problem......Page 128
3.5 Tree Analysis of Sorting Algorithms......Page 137
3.6 Summary and References......Page 141
4.1 Shortest Paths......Page 143
4.2 Network Flows......Page 147
4.3 Algorithmic Matching......Page 166
4.4 Summary and References......Page 176
PART TWO ENUMERATION......Page 179
5.1 Two Basic Counting Principles......Page 181
5.2 Simple Arrangements and Selections......Page 190
5.3 Arrangements and Selections with Repetition......Page 205
5.4 Distributions......Page 212
5.5 Binomial Identities......Page 223
5.6 Generating Permutations and Combinations and Programming Projects......Page 234
5.7 Summary and References......Page 241
Supplement: Selected Solutions to Problems in Chapter 5......Page 242
6.1 Generating Function Models......Page 253
6.2 Calculating Coefficients of Generating Functions......Page 260
6.3 Partitions......Page 270
6.4 Exponential Generating Functions......Page 276
6.5 A Summation Method......Page 282
6.6 Summary and References......Page 286
7.1 Recurrence Relation Models......Page 289
7.2 Divide-and-Conquer Relations......Page 303
7.3 Solution of Linear Recurrence Relations......Page 307
7.4 Solution of Inhomogeneous Recurrence Relations......Page 311
7.5 Solutions with Generating Functions......Page 316
7.6 Summary and References......Page 325
8.1 Counting with Venn Diagrams......Page 327
8.2 Inclusion-Exclusion Formula......Page 335
8.3 Restricted Positions and Rook Polynomials......Page 347
8.4 Summary and Reference......Page 357
PART THREE ADDITIONAL TOPICS......Page 359
9.1 Equivalence and Symmetry Groups......Page 361
9.2 Burnside's Theorem......Page 369
9.3 The Cycle Index......Page 375
9.4 Polya's Formula......Page 382
9.5 Summary and References......Page 389
10.1 Graph Model for Instant Insanity......Page 391
10.2 Progressively Finite Games......Page 397
10.3 Nim-Type Games......Page 406
10.4 Summary and References......Page 413
A.1 Set Theory and Logic......Page 415
A.2 Mathematical Induction......Page 421
A.3 A Little Probability......Page 425
A.4 The Pigeonhole Principle......Page 429
GLOSSARY OF COUNTING AND GRAPH THEORY TERMS......Page 433
BIBLIOGRAPHY......Page 439
SOLUTIONS TO ODD-NUMBERED PROBLEMS......Page 441
INDEX......Page 467