Foundations of Combinatorics with Applications

Contents iii Preface ix Part I Counting and Listing 1(118) Preliminary Reading 2(3) Basic Counting 5(36) Introduction 5(1) Lists with Repetitions Allowed 6(5) Using the Rules of Sum and Product 9(1) Exercises 10(1) Lists with Repetitions Forbidden 11(8) Exercises 17(2) Sets 19(13) Error Correcting Codes 27(3) Exercises 30(2) Recursions 32(4) Exercises 35(1) Multisets 36(5) Exercises 38(1) Notes and References 39(2) Functions 41(24) Introduction 41(1) Some Basic Terminology 41(4) Terminology for Sets 41(1) What are Functions? 42(2) Exercises 44(1) Permutations 45(6) Exercises 50(1) Other Combinatorial Aspects of Functions 51(8) Monotonic Functions and Unordered Lists 51(3) Image and Coimage 54(1) The Pigeonhole Principle 55(2) Exercises 57(2) Boolean Functions 59(6) Exercises 63(1) Notes and References 64(1) Decision Trees 65(28) Introduction 65(1) Basic Concepts of Decision Trees 65(10) Exercises 73(2) Ranking and Unranking 75(9) Calculating RANK 76(3) Calculating UNRANK 79(2) Gray Codes 81(2) Exercises 83(1) Backtracking 84(9) Exercises 90(1) Notes and References 91(2) Sieving Methods 93(26) Introduction 93(1) Structures Lacking Things 93(1) Structures with Symmetries 94(1) The Principle of Inclusion and Exclusion 94(12) Exercises 100(2) Bonferroni's Inequalities 102(1) Partially Ordered Sets 103(1) Exercises 104(2) Listing Structures with Symmetries 106(5) Exercises 109(2) Counting Structures with Symmetries 111(8) Proofs 114(2) Exercises 116(1) Notes and References 117(2) Part II Graphs 119(76) Basic Concepts in Graph Theory 121(28) Introduction 121(1) What is a Graph? 121(5) Exercises 124(2) Equivalence Relations and Unlabeled Graphs 126(5) Exercises 130(1) Paths and Subgraphs 131(5) Exercises 134(2) Trees 136(5) Exercises 139(2) Directed Graphs (Digraphs) 141(5) Exercises 144(2) Computer Representations of Graphs 146(3) Exercises 146(1) Notes and References 147(2) A Sampler of Graph Topics 149(46) Introduction 149(1) Spanning Trees 150(7) Minimum Weight Spanning Trees 150(3) Lineal Spanning Trees 153(2) Exercises 155(2) Coloring Graphs 157(5) Exercises 161(1) Planar Graphs 162(8) Euler's Relation 163(1) Exercises 164(1) The Five Color Theorem 165(1) Exercises 166(1) Algorithmic Questions 167(2) Exercises 169(1) Flows in Networks 170(10) The Concepts 170(3) An Algorithm for Constructing a Maximum Flow 173(3) Exercises 176(1) Cut Partitions and Cut Sets 176(3) Exercises 179(1) Probability and Simple Graphs 180(8) Exercises 186(2) Finite State Machines 188(7) Turing Machines 188(1) Finite State Machines and Digraphs 189(3) Exercises 192(2) Notes and References 194(1) Part III Recursion 195(72) Induction and Recursion 197(30) Introduction 197(1) Inductive Proofs and Recursive Equations 198(6) Exercises 203(1) Thinking Recursively 204(6) Exercises 209(1) Recursive Algorithms 210(10) Obtaining Information: Merge Sorting 210(2) Local Descriptions 212(3) Computer Implementation 215(2) Exercises 217(3) Divide and Conquer 220(7) Exercises 223(2) Notes and References 225(2) Sorting Theory 227(20) Introduction 227(1) Limits on Speed 228(4) Motivation and Proof of the Theorem 229(2) Exercises 231(1) Software Sorts 232(6) Binary Insertion Sort 233(1) Bucket Sort 234(1) Merge Sorts 235(1) Quicksort 235(1) Heapsort 236(1) Exercises 237(1) Sorting Networks 238(9) Speed and Cost 238(1) Parallelism 239(1) How Fast Can a Network Be? 240(1) How Cheap Can a Network Be? 240(1) Exercises 240(1) Proving That a Network Sorts 241(2) The Batcher Sort 243(1) Exercises 244(1) Notes and References 245(2) Rooted Plane Trees 247(20) Introduction 247(1) Traversing Trees 248(5) Depth First Traversals 249(2) Exercises 251(2) Grammars and RP-Trees 253(6) Exercises 258(1) Unlabeled Full Binary RP-Trees 259(8) Exercises 265(1) Notes and References 266(1) Part IV Generating Functions 267(94) Ordinary Generating Functions 269(38) Introduction 269(1) What are Generating Functions? 269(6) Exercises 273(2) Solving a Single Recursion 275(7) Exercises 280(2) Manipulating Generating Functions 282(9) Obtaining Recursions 282(2) Derivatives, Averages and Probability 284(7) Exercises 291(1) The Rules of Sum and Product 291(16) Exercises 298(6) Notes and References 304(3) Generating Function Topics 307(54) Introduction 307(1) Systems of Recursions 308(7) Exercises 313(2) Exponential Generating Functions 315(15) The Exponential Formula 320(6) Exercises 326(4) Symmetries and Polya's Theorem 330(9) Exercises 338(1) Asymptotic Estimates 339(22) Recursions 341(3) Sums of Positive Terms 344(5) Generating Functions 349(6) Exercises 355(4) Notes and References 359(2) Appendix A Induction 361(6) Exercises 365(2) Appendix B Rates of Growth and Analysis of Algorithms 367(14) B.1 The Basic Functions 368(8) Exercises 374(2) B.2 Doing Arithmetic 376(1) B.3 NP-Complete Problems 377(4) Exercises 379(1) Notes and References 380(1) Appendix C Basic Probability 381(6) C.1 Probability Spaces and Random Variables 381(3) C.2 Expectation and Variance 384(3) Appendix D Partial Fractions 387(6) Theory 387(1) Computations 388(5) Solutions to Odd Exercises and Most Appendix Exercises 393(68) Index 461