| |
| |
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 | |