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

One Step at a Time. The Method of Mathematical Induction | p. 21 |

Weak Induction | p. 21 |

Strong Induction | p. 26 |

Exercises | p. 28 |

Supplementary Exercises | p. 30 |

Solutions to Exercises | p. 31 |

Enumerative Combinatorics | |

There Are A Lot Of Them. Elementary Counting Problems | p. 39 |

Permutations | p. 39 |

Strings over a Finite Alphabet | p. 42 |

Choice Problems | p. 45 |

Exercises | p. 49 |

Supplementary Exercises | p. 53 |

Solutions to Exercises | p. 55 |

No Matter How You Slice It. The Binomial Theorem and Related Identities | p. 67 |

The Binomial Theorem | p. 67 |

The Multinomial Theorem | p. 72 |

When the Exponent Is Not a Positive Integer | p. 74 |

Exercises | p. 76 |

Supplementary Exercises | p. 79 |

Solutions to Exercises | p. 82 |

Divide and Conquer. Partitions | p. 93 |

Compositions | p. 93 |

Set Partitions | p. 95 |

Integer Partitions | p. 98 |

Exercises | p. 105 |

Supplementary Exercises | p. 106 |

Solutions to Exercises | p. 108 |

Not So Vicious Cycles. Cycles in Permutations | p. 113 |

Cycles in Permutations | p. 114 |

Permutations with Restricted Cycle Structure | p. 120 |

Exercises | p. 124 |

Supplementary Exercises | p. 126 |

Solutions to Exercises | p. 129 |

You Shall Not Overcount. The Sieve | p. 135 |

Enumerating The Elements of Intersecting Sets | p. 135 |

Applications of the Sieve Formula | p. 138 |

Exercises | p. 142 |

Supplementary Exercises | p. 143 |

Solutions to Exercises | p. 144 |

A Function Is Worth Many Numbers. Generating Functions | p. 149 |

Ordinary Generating Functions | p. 149 |

Recurrence Relations and Generating Functions | p. 149 |

Products of Generating Functions | p. 156 |

Compositions of Generating Functions | p. 163 |

Exponential Generating Functions | p. 166 |

Recurrence Relations and Exponential Generating Functions | p. 166 |

Products of Exponential Generating Functions | p. 168 |

Compositions of Exponential Generating Functions | p. 171 |

Exercises | p. 174 |

Supplementary Exercises | p. 176 |

Solutions to Exercises | p. 178 |

Graph Theory | |

Dots and Lines. The Origins of Graph Theory | p. 189 |

The Notion of Graphs. Eulerian Trails | p. 189 |

Hamiltonian Cycles | p. 194 |

Directed Graphs | p. 196 |

The Notion of Isomorphisms | p. 199 |

Exercises | p. 202 |

Supplementary Exercises | p. 205 |

Solutions to Exercises | p. 208 |

Staying Connected. Trees | p. 215 |

Minimally Connected Graphs | p. 215 |

Minimum-weight Spanning Trees. Kruskal's Greedy Algorithm | p. 221 |

Graphs and Matrices | p. 225 |

Adjacency Matrices of Graphs | p. 225 |

The Number of Spanning Trees of a Graph | p. 228 |

Exercises | p. 233 |

Supplementary Exercises | p. 236 |

Solutions to Exercises | p. 238 |

Finding A Good Match. Coloring and Matching | p. 247 |

Introduction | p. 247 |

Bipartite Graphs | p. 249 |

Matchings in Bipartite Graphs | p. 254 |

More Than Two Color | p. 260 |

Matchings in Graphs That Are Not Bipartite | p. 262 |

Exercises | p. 266 |

Supplementary Exercises | p. 267 |

Solutions to Exercises | p. 269 |

Do Not Cross. Planar Graphs | p. 275 |

Euler's Theorem for Planar Graphs | p. 275 |

Polyhedra | p. 278 |

Coloring Maps | p. 285 |

Exercises | p. 287 |

Supplementary Exercises | p. 288 |

Solutions to Exercises | p. 290 |

Horizons | |

Does It Clique? Ramsey Theory | p. 293 |

Ramsey Theory for Finite Graphs | p. 293 |

Generalizations of the Ramsey Theorem | p. 298 |

| |

Exercises | p. 304 |

Supplementary Exercises | p. 305 |

Solutions to Exercises | p. 307 |

So Hard To Avoid. Subsequence Conditions on Permutations | p. 313 |

Pattern Avoidance | p. 313 |

Stack Sortable Permutations | p. 322 |

Exercises | p. 334 |

Supplementary Exercises | p. 335 |

Solutions to Exercises | p. 338 |

Who Knows What It Looks Like, But It Exists. The Probabilistic Method | p. 349 |

The Notion of Probability | p. 349 |

Non-constructive Proofs | p. 352 |

Independent Events | p. 355 |

The Notion of Independence and Bayes' Theorem | p. 355 |

More Than Two Events | p. 359 |

Expected Values | p. 360 |

Linearity of Expectation | p. 361 |

Existence Proofs Using Expectation | p. 364 |

Conditional Expectation | p. 365 |

Exercises | p. 367 |

Supplementary Exercises | p. 370 |

Solutions to Exercises | p. 373 |

At Least Some Order. Partial Orders and Lattices | p. 381 |

The Notion of Partially Ordered Sets | p. 381 |

The Möbius Function of a Poset | p. 387 |

Lattices | p. 394 |

Exercises | p. 401 |

Supplementary Exercises | p. 403 |

Solutions to Exercises | p. 406 |

As Evenly As Possible. Block Designs and Error Correcting Codes | p. 413 |

Introduction | p. 413 |

Moto-cross Races | p. 413 |

Incompatible Computer Programs | p. 415 |

Balanced Incomplete Block Designs | p. 417 |

New Designs From Old | p. 419 |

Existence of Certain BIBDs | p. 424 |

A Derived Design of a Projective Plane | p. 426 |

Codes and Designs | p. 427 |

Coding Theory | p. 427 |

Error Correcting Codes | p. 427 |

Formal Definitions on Codes | p. 429 |

Exercises | p. 436 |

Supplementary Exercises | p. 438 |

Solutions to Exercises | p. 440 |

Are They Really Different? Counting Unlabeled Structures | p. 447 |

Enumeration Under Group Action | p. 447 |

Introduction | p. 447 |

Groups | p. 448 |

Permutation Groups | p. 450 |

Counting Unlabeled Trees | p. 457 |

Counting Rooted Non-plane 1-2 trees | p. 457 |

Counting Rooted Non-plane Trees | p. 460 |

Counting Unrooted Trees | p. 463 |

Exercises | p. 469 |

Supplementary Exercises | p. 472 |

Solutions to Exercises | p. 474 |

The Sooner The Better Combinatorial Algorithms | p. 481 |

In Lieu of Definitions | p. 481 |

The Halting Problem | p. 482 |

Sorting Algorithms | p. 483 |

BubbleSort | p. 483 |

MergeSort | p. 486 |

Comparing the Growth of Functions | p. 490 |

Algorithms on Graphs | p. 491 |

Minimum-cost Spanning Trees, Revisited | p. 491 |

Finding the Shortest Path | p. 495 |

Exercises | p. 500 |

Supplementary Exercises | p. 502 |

Solutions to Exercises | p. 503 |

Does Many Mean More Than One? Computational Complexity | p. 509 |

Turing Machines | p. 509 |

Complexity Classes | p. 512 |

The Class P | p. 512 |

The Class NP | p. 514 |

NP-complete Problems | p. 521 |

Other Complexity Classes | p. 526 |

Exercises | p. 529 |

Supplementary Exercises | p. 531 |

Solutions to Exercises | p. 532 |

Bibliography | p. 537 |

Index | p. 541 |

Table of Contents provided by Ingram. All Rights Reserved. |