| |
| |
| Foreword | |
| |
| |
| Preface | |
| |
| |
| Acknowledgments | |
| |
| |
| I How: Methods | |
| |
| |
| |
| Basic Methods | |
| |
| |
| |
| When We Add and When We Subtract | |
| |
| |
| |
| When We Add | |
| |
| |
| |
| When We Subtract | |
| |
| |
| |
| When We Multiply | |
| |
| |
| |
| The Product Principle | |
| |
| |
| |
| Using Several Counting Principles | |
| |
| |
| |
| When Repetitions Are Not Allowed | |
| |
| |
| |
| When We Divide | |
| |
| |
| |
| The Division Principle | |
| |
| |
| |
| Subsets | |
| |
| |
| |
| Applications of Basic Counting Principles | |
| |
| |
| |
| Bijective Proofs | |
| |
| |
| |
| Properties of Binomial Coefficients | |
| |
| |
| |
| Permutations With Repetition | |
| |
| |
| |
| The Pigeonhole Principle | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Chapter Review | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Solutions to Exercises | |
| |
| |
| |
| Supplementary Exercises | |
| |
| |
| |
| Direct Applications of Basic Methods | |
| |
| |
| |
| Multisets and Compositions | |
| |
| |
| |
| Weak Compositions | |
| |
| |
| |
| Compositions | |
| |
| |
| |
| Set Partitions | |
| |
| |
| |
| Stirling Numbers of the Second Kind | |
| |
| |
| |
| Recurrence Relations for Stirling Numbers of the Second Kind | |
| |
| |
| |
| When the Number of Blocks Is Not Fixed | |
| |
| |
| |
| Partitions of Integers | |
| |
| |
| |
| Nonincreasing Finite Sequences of Integers | |
| |
| |
| |
| Ferrers Shapes and Their Applications | |
| |
| |
| |
| Excursion: Euler’s Pentagonal Number Theorem | |
| |
| |
| |
| The Inclusion-Exclusion Principle | |
| |
| |
| |
| Two Intersecting Sets | |
| |
| |
| |
| Three Intersecting Sets | |
| |
| |
| |
| Any Number of Intersecting Sets | |
| |
| |
| |
| The Twelvefold Way | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Chapter Review | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Solutions to Exercises | |
| |
| |
| |
| Supplementary Exercises | |
| |
| |
| |
| Generating Functions | |
| |
| |
| |
| Power Series | |
| |
| |
| |
| Generalized Binomial Coefficients | |
| |
| |
| |
| Formal Power Series | |
| |
| |
| |
| Warming Up: Solving Recursions | |
| |
| |
| |
| Ordinary Generating Functions | |
| |
| |
| |
| Exponential Generating Functions | |
| |
| |
| |
| Products of Generating Functions | |
| |
| |
| |
| Ordinary Generating Functions | |
| |
| |
| |
| Exponential Generating Functions | |
| |
| |
| |
| Excursion: Composition of Two Generating Functions | |
| |
| |
| |
| Ordinary Generating Functions | |
| |
| |
| |
| Exponential Generating Functions | |
| |
| |
| |
| Excursion: A Different Type of Generating Function | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Chapter Review | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Solutions to Exercises | |
| |
| |
| |
| Supplementary Exercises II What: Topics | |
| |
| |
| |
| Counting Permutations | |
| |
| |
| |
| Eulerian Numbers | |
| |
| |
| |
| The Cycle Structure of Permutations | |
| |
| |
| |
| Stirling Numbers of the First Kind | |
| |
| |
| |
| Permutations of a Given Type | |
| |
| |
| |
| Cycle Structure and Exponential Generating Functions | |
| |
| |
| |
| Inversions | |
| |
| |
| |
| Counting Permutations with Respect to Inversions | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Chapter Review | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Solutions to Exercises | |
| |
| |
| |
| Supplementary Exercises | |
| |
| |
| |
| Counting Graphs | |
| |
| |
| |
| Counting Trees and Forests | |
| |
| |
| |
| Counting Trees | |
| |
| |
| |
| The Notion of Graph Isomorphisms | |
| |
| |
| |
| Counting Trees on Labeled Vertices | |
| |
| |
| |
| Counting Forests | |
| |
| |
| |
| Graphs and Functions | |
| |
| |
| |
| Acyclic Functions | |
| |
| |
| |
| Parking Functions | |
| |
| |
| |
| When the Vertices Are Not Freely Labeled | |
| |
| |
| |
| Rooted Plane Trees | |
| |
| |
| |
| Binary Plane Trees | |
| |
| |
| |
| Excursion: Graphs on Colored Vertices | |
| |
| |
| |
| Chromatic Polynomials | |
| |
| |
| |
| Counting k-colored Graphs | |
| |
| |
| |
| Graphs and Generating Functions | |
| |
| |
| |
| Generating Functions of Trees | |
| |
| |
| |
| Counting Connected Graphs | |
| |
| |
| |
| Counting Eulerian Graphs | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Chapter Review | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Solutions to Exercises | |
| |
| |
| |
| Supplementary Exercises | |
| |
| |
| |
| Extremal Combinatorics | |
| |
| |
| |
| Extremal Graph Theory | |
| |
| |
| |
| Bipartite Graphs | |
| |
| |
| |
| Tur�an’s Theorem | |
| |
| |
| |
| Graphs Excluding Cycles | |
| |
| |
| |
| Graphs Excluding Complete Bipartite Graphs | |
| |
| |
| |
| Hypergraphs | |
| |
| |
| |
| Hypergraphs with Pairwise Intersecting Edges | |
| |
| |
| |
| Hypergraphs with Pairwise Incomparable Edges | |
| |
| |
| |
| Something Is More Than Nothing: Existence Proofs | |
| |
| |
| |
| Property B | |
| |
| |
| |
| Excluding Monochromatic Arithmetic Progressions | |
| |
| |
| |
| Codes Over Finite Alphabets | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Chapte | |