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