| Foreword | p. vii |
| Preface | p. ix |
| Acknowledgments | p. xi |
| Basic Methods | |
| Seven Is More Than Six. The Pigeon-Hole Principle | p. 1 |
| The Basic Pigeon-Hole Principle | p. 1 |
| The Generalized Pigeon-Hole Principle | p. 3 |
| Exercises | p. 9 |
| Supplementary Exercises | p. 11 |
| Solutions to Exercises | p. 12 |
| One Step at a Time. The Method of Mathematical Induction | p. 19 |
| Weak Induction | p. 19 |
| Strong Induction | p. 24 |
| Exercises | p. 26 |
| Supplementary Exercises | p. 28 |
| Solutions to Exercises | p. 29 |
| Enumerative Combinatorics | |
| There Are A Lot Of Them. Elementary Counting Problems | p. 37 |
| Permutations | p. 37 |
| Strings over a Finite Alphabet | p. 40 |
| Choice Problems | p. 43 |
| Exercises | p. 47 |
| Supplementary Exercises | p. 51 |
| Solutions to Exercises | p. 53 |
| No Matter How You Slice It. The Binomial Theorem and Related Identities | p. 65 |
| The Binomial Theorem | p. 65 |
| The Multinomial Theorem | p. 70 |
| When the Exponent Is Not a Positive Integer | p. 72 |
| Exercises | p. 74 |
| Supplementary Exercises | p. 77 |
| Solutions to Exercises | p. 80 |
| Divide and Conquer. Partitions | p. 89 |
| Compositions | p. 89 |
| Set Partitions | p. 91 |
| Integer Partitions | p. 94 |
| Exercises | p. 101 |
| Supplementary Exercises | p. 102 |
| Solutions to Exercises | p. 103 |
| Not So Vicious Cycles. Cycles in Permutations | p. 109 |
| Cycles in Permutations | p. 110 |
| Permutations with Restricted Cycle Structure | p. 115 |
| Exercises | p. 120 |
| Supplementary Exercises | p. 122 |
| Solutions to Exercises | p. 124 |
| You Shall Not Overcount. The Sieve | p. 131 |
| Enumerating The Elements of Intersecting Sets | p. 131 |
| Applications of the Sieve Formula | p. 134 |
| Exercises | p. 138 |
| Supplementary Exercises | p. 139 |
| Solutions to Exercises | p. 139 |
| A Function Is Worth Many Numbers. Generating Functions | p. 145 |
| Ordinary Generating Functions | p. 145 |
| Recurrence Relations and Generating Functions | p. 145 |
| Products of Generating Functions | p. 152 |
| Compositions of Generating Functions | p. 157 |
| Exponential Generating Functions | p. 160 |
| Recurrence Relations and Exponential Generating Functions | p. 160 |
| Products of Exponential Generating Functions | p. 162 |
| Compositions of Exponential Generating Functions | p. 164 |
| Exercises | p. 167 |
| Supplementary Exercises | p. 169 |
| Solutions to Exercises | p. 172 |
| Graph Theory | |
| Dots and Lines. The Origins of Graph Theory | p. 183 |
| The Notion of Graphs. Eulerian Walks | p. 183 |
| Hamiltonian Cycles | p. 188 |
| Directed Graphs | p. 190 |
| The Notion of Isomorphisms | p. 193 |
| Exercises | p. 196 |
| Supplementary Exercises | p. 199 |
| Solutions to Exercises | p. 201 |
| Staying Connected. Trees | p. 209 |
| Minimally Connected Graphs | p. 209 |
| Minimum-weight Spanning Trees. Kruskal's Greedy Algorithm | p. 216 |
| Graphs and Matrices | p. 220 |
| Adjacency Matrices of Graphs | p. 220 |
| The Number of Spanning Trees of a Graph | p. 223 |
| Exercises | p. 228 |
| Supplementary Exercises | p. 230 |
| Solutions to Exercises | p. 232 |
| Finding A Good Match. Coloring and Matching | p. 241 |
| Introduction | p. 241 |
| Bipartite Graphs | p. 243 |
| Matchings in Bipartite Graphs | p. 248 |
| More Than Two Colors | p. 254 |
| Matchings in Graphs That Are Not Bipartite | p. 256 |
| Exercises | p. 259 |
| Supplementary Exercises | p. 261 |
| Solutions to Exercises | p. 262 |
| Do Not Cross. Planar Graphs | p. 269 |
| Euler's Theorem for Planar Graphs | p. 269 |
| Polyhedra | p. 272 |
| Coloring Maps | p. 279 |
| Exercises | p. 281 |
| Supplementary Exercises | p. 282 |
| Solutions to Exercises | p. 283 |
| Horizons | |
| Does It Clique? Ramsey Theory | p. 287 |
| Ramsey Theory for Finite Graphs | p. 287 |
| Generalizations of the Ramsey Theorem | p. 292 |
| Ramsey Theory in Geometry | p. 295 |
| Exercises | p. 298 |
| Supplementary Exercises | p. 299 |
| Solutions to Exercises | p. 301 |
| So Hard To Avoid. Subsequence Conditions on Permutations | p. 307 |
| Pattern Avoidance | p. 307 |
| Stack Sortable Permutations | p. 319 |
| Exercises | p. 330 |
| Supplementary Exercises | p. 331 |
| Solutions to Exercises | p. 333 |
| Who Knows What It Looks Like, But It Exists. The Probabilistic Method | p. 345 |
| The Notion of Probability | p. 345 |
| Non-constructive Proofs | p. 348 |
| Independent Events | p. 351 |
| The Notion of Independence and Bayes' Theorem | p. 351 |
| More Than Two Events | p. 355 |
| Expected Values | p. 356 |
| Linearity of Expectation | p. 357 |
| Existence Proofs Using Expectation | p. 360 |
| Conditional Expectation | p. 361 |
| Exercises | p. 363 |
| Supplementary Exercises | p. 365 |
| Solutions to Exercises | p. 368 |
| At Least Some Order. Partial Orders and Lattices | p. 375 |
| The Notion of Partially Ordered Sets | p. 375 |
| The Mobius Function of a Poset | p. 380 |
| Lattices | p. 388 |
| Exercises | p. 395 |
| Supplementary Exercises | p. 397 |
| Solutions to Exercises | p. 399 |
| The Sooner The Better. Combinatorial Algorithms | p. 407 |
| In Lieu of Definitions | p. 407 |
| The Halting Problem | p. 408 |
| Sorting Algorithms | p. 409 |
| BubbleSort | p. 409 |
| MergeSort | p. 412 |
| Comparing the Growth of Functions | p. 416 |
| Algorithms on Graphs | p. 417 |
| Minimum-cost Spanning Trees, Revisited | p. 417 |
| Finding the Shortest Path | p. 421 |
| Exercises | p. 426 |
| Supplementary Exercises | p. 428 |
| Solutions to Exercises | p. 428 |
| Does Many Mean More Than One? Computational Complexity | p. 433 |
| Turing Machines | p. 433 |
| Complexity Classes | p. 436 |
| The Class P | p. 436 |
| The Class NP | p. 438 |
| NP-complete Problems | p. 445 |
| Other Complexity Classes | p. 450 |
| Exercises | p. 453 |
| Supplementary Exercises | p. 454 |
| Solutions to Exercises | p. 455 |
| Bibliography | p. 461 |
| Index | p. 465 |
| Table of Contents provided by Ingram. All Rights Reserved. |
