| |
| |
Foreword | |
| |
| |
Preface | |
| |
| |
Acknowledgments | |
| |
| |
| |
Basic Methods | |
| |
| |
| |
Seven Is More Than Six. The Pigeon-Hole Principle | |
| |
| |
| |
The Basic Pigeon-Hole Principle | |
| |
| |
| |
The Generalized Pigeon-Hole Principle | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
One Step at a Time. The Method of Mathematical Induction | |
| |
| |
| |
Weak Induction | |
| |
| |
| |
Strong Induction | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Enumerative Combinatorics | |
| |
| |
| |
There Are A Lot Of Them. Elementary Counting Problems | |
| |
| |
| |
Permutations | |
| |
| |
| |
Strings over a Finite Alphabet | |
| |
| |
| |
Choice Problems | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
No Matter How You Slice It. The Binomial Theorem and Related Identities | |
| |
| |
| |
The Binomial Theorem | |
| |
| |
| |
The Multinomial Theorem | |
| |
| |
| |
When the Exponent Is Not a Positive Integer | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Divide and Conquer. Partitions | |
| |
| |
| |
Compositions | |
| |
| |
| |
Set Partitions | |
| |
| |
| |
Integer Partitions | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Not So Vicious Cycles. Cycles in Permutations | |
| |
| |
| |
Cycles in Permutations | |
| |
| |
| |
Permutations with Restricted Cycle Structure | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
You Shall Not Overcount. The Sieve | |
| |
| |
| |
Enumerating The Elements of Intersecting Sets | |
| |
| |
| |
Applications of the Sieve Formula | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
A Function Is Worth Many Numbers. Generating Functions | |
| |
| |
| |
Ordinary Generating Functions | |
| |
| |
| |
Recurrence Relations and Generating Functions | |
| |
| |
| |
Products of Generating Functions | |
| |
| |
| |
Compositions of Generating Functions | |
| |
| |
| |
Exponential Generating Functions | |
| |
| |
| |
Recurrence Relations and Exponential Generating Functions | |
| |
| |
| |
Products of Exponential Generating Functions | |
| |
| |
| |
Compositions of Exponential Generating Functions | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Graph Theory | |
| |
| |
| |
Dots and Lines. The Origins of Graph Theory | |
| |
| |
| |
The Notion of Graphs. Eulerian Trails | |
| |
| |
| |
Hamiltonian Cycles | |
| |
| |
| |
Directed Graphs | |
| |
| |
| |
The Notion of Isomorphisms | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Staying Connected. Trees | |
| |
| |
| |
Minimally Connected Graphs | |
| |
| |
| |
Minimum-weight Spanning Trees. Kruskal's Greedy Algorithm | |
| |
| |
| |
Graphs and Matrices | |
| |
| |
| |
Adjacency Matrices of Graphs | |
| |
| |
| |
The Number of Spanning Trees of a Graph | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Finding A Good Match. Coloring and Matching | |
| |
| |
| |
Introduction | |
| |
| |
| |
Bipartite Graphs | |
| |
| |
| |
Matchings in Bipartite Graphs | |
| |
| |
| |
More Than Two Color | |
| |
| |
| |
Matchings in Graphs That Are Not Bipartite | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Do Not Cross. Planar Graphs | |
| |
| |
| |
Euler's Theorem for Planar Graphs | |
| |
| |
| |
Polyhedra | |
| |
| |
| |
Coloring Maps | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Horizons | |
| |
| |
| |
Does It Clique? Ramsey Theory | |
| |
| |
| |
Ramsey Theory for Finite Graphs | |
| |
| |
| |
Generalizations of the Ramsey Theorem | |
| |
| |
| |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
So Hard To Avoid. Subsequence Conditions on Permutations | |
| |
| |
| |
Pattern Avoidance | |
| |
| |
| |
Stack Sortable Permutations | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Who Knows What It Looks Like, But It Exists. The Probabilistic Method | |
| |
| |
| |
The Notion of Probability | |
| |
| |
| |
Non-constructive Proofs | |
| |
| |
| |
Independent Events | |
| |
| |
| |
The Notion of Independence and Bayes' Theorem | |
| |
| |
| |
More Than Two Events | |
| |
| |
| |
Expected Values | |
| |
| |
| |
Linearity of Expectation | |
| |
| |
| |
Existence Proofs Using Expectation | |
| |
| |
| |
Conditional Expectation | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
At Least Some Order. Partial Orders and Lattices | |
| |
| |
| |
The Notion of Partially Ordered Sets | |
| |
| |
| |
The M�bius Function of a Poset | |
| |
| |
| |
Lattices | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
As Evenly As Possible. Block Designs and Error Correcting Codes | |
| |
| |
| |
Introduction | |
| |
| |
| |
Moto-cross Races | |
| |
| |
| |
Incompatible Computer Programs | |
| |
| |
| |
Balanced Incomplete Block Designs | |
| |
| |
| |
New Designs From Old | |
| |
| |
| |
Existence of Certain BIBDs | |
| |
| |
| |
A Derived Design of a Projective Plane | |
| |
| |
| |
Codes and Designs | |
| |
| |
| |
Coding Theory | |
| |
| |
| |
Error Correcting Codes | |
| |
| |
| |
Formal Definitions on Codes | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Are They Really Different? Counting Unlabeled Structures | |
| |
| |
| |
Enumeration Under Group Action | |
| |
| |
| |
Introduction | |
| |
| |
| |
Groups | |
| |
| |
| |
Permutation Groups | |
| |
| |
| |
Counting Unlabeled Trees | |
| |
| |
| |
Counting Rooted Non-plane 1-2 trees | |
| |
| |
| |
Counting Rooted Non-plane Trees | |
| |
| |
| |
Counting Unrooted Trees | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
The Sooner The Better Combinatorial Algorithms | |
| |
| |
| |
In Lieu of Definitions | |
| |
| |
| |
The Halting Problem | |
| |
| |
| |
Sorting Algorithms | |
| |
| |
| |
BubbleSort | |
| |
| |
| |
MergeSort | |
| |
| |
| |
Comparing the Growth of Functions | |
| |
| |
| |
Algorithms on Graphs | |
| |
| |
| |
Minimum-cost Spanning Trees, Revisited | |
| |
| |
| |
Finding the Shortest Path | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
| |
Does Many Mean More Than One? Computational Complexity | |
| |
| |
| |
Turing Machines | |
| |
| |
| |
Complexity Classes | |
| |
| |
| |
The Class P | |
| |
| |
| |
The Class NP | |
| |
| |
| |
NP-complete Problems | |
| |
| |
| |
Other Complexity Classes | |
| |
| |
Exercises | |
| |
| |
Supplementary Exercises | |
| |
| |
Solutions to Exercises | |
| |
| |
Bibliography | |
| |
| |
Index | |