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