Foreword Preface Acknowledgments I How: Methods 1 Basic Methods 1.1 When We Add and When We Subtract 1.1.1 When We Add 1.1.2 When We Subtract 1.2 When We Multiply 1.2.

1 The Product Principle 1.2.2 Using Several Counting Principles 1.2.3 When Repetitions Are Not Allowed 1.3 When We Divide 1.3.1 The Division Principle 1.

3.2 Subsets 1.4 Applications of Basic Counting Principles 1.4.1 Bijective Proofs 1.4.2 Properties of Binomial Coefficients 1.4.

3 Permutations With Repetition 1.5 The Pigeonhole Principle 1.6 Notes 1.7 Chapter Review 1.8 Exercises 1.9 Solutions to Exercises 1.10 Supplementary Exercises 2 Direct Applications of Basic Methods 2.1 Multisets and Compositions 2.

1.1 Weak Compositions 2.1.2 Compositions 2.2 Set Partitions 2.2.1 Stirling Numbers of the Second Kind 2.2.

2 Recurrence Relations for Stirling Numbers of the Second Kind 2.2.3 When the Number of Blocks Is Not Fixed 2.3 Partitions of Integers 2.3.1 Nonincreasing Finite Sequences of Integers 2.3.2 Ferrers Shapes and Their Applications 2.

3.3 Excursion: Euler's Pentagonal Number Theorem 2.4 The Inclusion-Exclusion Principle 2.4.1 Two Intersecting Sets 2.4.2 Three Intersecting Sets 2.4.

3 Any Number of Intersecting Sets 2.5 The Twelvefold Way 2.6 Notes 2.7 Chapter Review 2.8 Exercises 2.9 Solutions to Exercises 2.10 Supplementary Exercises 3 Generating Functions 3.1 Power Series 3.

1.1 Generalized Binomial Coefficients 3.1.2 Formal Power Series 3.2 Warming Up: Solving Recursions 3.2.1 Ordinary Generating Functions 3.2.

2 Exponential Generating Functions 3.3 Products of Generating Functions 3.3.1 Ordinary Generating Functions 3.3.2 Exponential Generating Functions 3.4 Excursion: Composition of Two Generating Functions 3.4.

1 Ordinary Generating Functions 3.4.2 Exponential Generating Functions 3.5 Excursion: A Different Type of Generating Function 3.6 Notes 3.7 Chapter Review 3.8 Exercises 3.9 Solutions to Exercises 3.

10 Supplementary Exercises II What: Topics 4 Counting Permutations 4.1 Eulerian Numbers 4.2 The Cycle Structure of Permutations 4.2.1 Stirling Numbers of the First Kind 4.2.2 Permutations of a Given Type 4.3 Cycle Structure and Exponential Generating Functions 4.

4 Inversions 4.4.1 Counting Permutations with Respect to Inversions 4.5 Notes 4.6 Chapter Review 4.7 Exercises 4.8 Solutions to Exercises 4.9 Supplementary Exercises 5 Counting Graphs 5.

1 Counting Trees and Forests 5.1.1 Counting Trees 5.2 The Notion of Graph Isomorphisms 5.3 Counting Trees on Labeled Vertices 5.3.1 Counting Forests 5.4 Graphs and Functions 5.

4.1 Acyclic Functions 5.4.2 Parking Functions 5.5 When the Vertices Are Not Freely Labeled 5.5.1 Rooted Plane Trees 5.5.

2 Binary Plane Trees 5.6 Excursion: Graphs on Colored Vertices 5.6.1 Chromatic Polynomials 5.6.2 Countingk-colored Graphs 5.7 Graphs and Generating Functions 5.7.

1 Generating Functions of Trees 5.7.2 Counting Connected Graphs 5.7.3 Counting Eulerian Graphs 5.8 Notes 5.9 Chapter Review 5.10 Exercises 5.

11 Solutions to Exercises 5.12 Supplementary Exercises 6 Extremal Combinatorics 6.1 Extremal Graph Theory 6.1.1 Bipartite Graphs 6.1.2 Tur'an's Theorem 6.1.

3 Graphs Excluding Cycles 6.1.4 Graphs Excluding Complete Bipartite Graphs 6.2 Hypergraphs 6.2.1 Hypergraphs with Pairwise Intersecting Edges 6.2.2 Hypergraphs with Pairwise Incomparable Edges 6.

3 Something Is More Than Nothing: Existence Proofs 6.3.1 Property B 6.3.2 Excluding Monochromatic Arithmetic Progressions 6.3.3 Codes Over Finite Alphabets 6.4 Notes 6.

5 Chapter Review 6.6 Exercises 6.7 Solutions to Exercises 6.8 Supplementary Exercises III What Else: Special Topics 7 Symmetric Structures 7.1 Hy.