CHAPTER 1 Counting 1
1.1 Basic Counting 1
The Sum Principle 1
Abstraction 3
Summing Consecutive Integers 3
The Product Principle 4
Two-Element Subsets 6
Important Concepts，Formulas，and Theorems 7
Problems 8
1.2 Counting Lists，Permutations，and Subsets 10
Using the Sum and Product Principles 10
Lists and Functions 12
The Bijection Principle 14
k-Element Permutations of a Set 15
Counting Subsets of a Set 16
Important Concepts，Formulas，and Theorems 18
Problems 20
1.3 Binomial Coefficients 22
Pascal’s Triangle 22
A Proof Using the Sum Principle 24
The Binomial Theorem 26
Labeling and Trinomial Coefficients 28
Important Concepts，Formulas，and Theorems 29
Problems 30
1.4 Relations 32
What Is a Relation？ 32
Functions as Relations 33
Properties of Relations 33
Equivalence Relations 36
Partial and Total Orders 39
Important Concepts，Formulas，and Theorems 41
Problems 42
1.5 Using Equivalence Relations in Counting 43
The Symmetry Principle 43
Equivalence Relations 45
The Quotient Principle 46
Equivalence Class Counting 46
Multi sets 48
The Bookcase Arrangement Problem 50
The Number of k-Element Multisets of an n-Element Set 51
Using the Quotient Principle to Explain a Quotient 52
Important Concepts，Formulas，and Theorems 53
Problems 54
CHAPTER 2 Cryptography and Number Theory 59
2.1 Cryptography and Modular Arithmetic 59
Introduction to Cryptography 59
Private-Key Cryptography 60
Public-Key Cryptosystems 63
Arithmetic Modulo n 65
Cryptography Using Addition mod n 68
Cryptography Using Multiplication mod n 69
Important Concepts，Formulas，and Theorems 71
Problems 72
2.2 Inverses and Greatest Common Divisors 75
Solutions to Equations and Inverses mod n 75
Inverses mod n 76
Converting Modular Equations to Normal Equations 79
Greatest Common Divisors 80
Euclid’s Division Theorem 81
Euclid’s GCD Algorithm 84
Extended GCD Algorithm 85
Computing Inverses 88
Important Concepts，Formulas，and Theorems 89
Problems 90
2.3 The RSA Cryptosystem 93
Exponentiation mod n 93
The Rules of Exponents 93
Fermat’s Little Theorem 96
The RSA Cryptosystem 97
The Chinese Remainder Theorem 101
Important Concepts，Formulas，and Theorems 102
Problems 104
2.4 Details of the RSA Cryptosystem 106
Practical Aspects of Exponentiation mod n 106
How Long Does It Take to Use the RSA Algorithm？ 109
How Hard Is Factoring？ 110
Finding Large Primes 110
Important Concepts，Formulas，and Theorems 113
Problems 114
CHAPTER 3 Reflections on Logic and Proof 117
3.1 Equivalence and Implication 117
Equivalence of Statements 117
Truth Tables 120
DeMorgan’s Laws 123
Implication 125
If and Only If 126
Important Concepts，Formulas，and Theorems 129
Problems 131
3.2 Variables and Quantifiers 133
Variables and Universes 133
Quantifiers 134
Standard Notation for Quantification 136
Statements about Variables 138
Rewriting Statements to Encompass Larger Universes 138
Proving Quantified Statements True or False 139
Negation of Quantified Statements 140
Implicit Quantification 143
Proof of Quantified Statements 144
Important Concepts，Formulas，and Theorems 145
Problems 147
3.3 Inference 149
Direct Inference （Modus Ponens） and Proofs 149
Rules of Inference for Direct Proofs 151
Contrapositive Rule of Inference 153
Proof by Contradiction 155
Important Concepts，Formulas，and Theorems 158
Problems 159
CHAPTER 4 Induction，Recursion，and Recurrences 161
4.1 Mathematical Induction 161
Smallest Counterexamples 161
The Principle of Mathematical Induction 165
Strong Induction 169
Induction in General 171
A Recursive View of Induction 173
Structural Induction 176
Important Concepts，Formulas，and Theorems 178
Problems 180
4.2 Recursion，Recurrences，and Induction 183
Recursion 183
Examples of First-Order Linear Recurrences 185
Iterating a Recurrence 187
Geometric Series 188
First-Order Linear Recurrences 191
Important Concepts，Formulas，and Theorems 195
Problems 197
4.3 Growth Rates of Solutions to Recurrences 198
Divide and Conquer Algorithms 198
Recursion Trees 201
Three Different Behaviors 209
Important Concepts，Formulas，and Theorems 210
Problems 212
4.4 The Master Theorem 214
Master Theorem 214
Solving More General Kinds of Recurrences 217
Extending the Master Theorem 218
Important Concepts，Formulas，and Theorems 220
Problems 221
4.5 More General Kinds of Recurrences 222
Recurrence Inequalities 222
The Master Theorem for Inequalities 223
A Wrinkle with Induction 225
Further Wrinkles in Induction Proofs 227
Dealing with Functions Other Than nc 230
Important Concepts，Formulas，and Theorems 232
Problems 233
4.6 Recurrences and Selection 235
The Idea of Selection 235
A Recursive Selection Algorithm 236
Selection without Knowing the Median in Advance 237
An Algorithm to Find an Element in the Middle Half 239
An Analysis of the Revised Selection Algorithm 242
Uneven Divisions 244
Important Concepts，Formulas，and Theorems 246
Problems 247
CHAPTER 5 Probability 249
5.1 Introduction to Probability 249
Why Study Probability？ 249
Some Examples of Probability Computations 252
Complementary Probabilities 253
Probability and Hashing 254
The Uniform Probability Distribution 256
Important Concepts，Formulas，and Theorems 259
Problems 260
5.2 Unions and Intersections 262
The Probability of a Union of Events 262
Principle of Inclusion and Exclusion for Probability 265
The Principle of Inclusion and Exclusion for Counting 271
Important Concepts，Formulas，and Theorems 273
Problems 274
5.3 Conditional Probability and Independence 276
Conditional Probability 276
Bayes’ Theorem 280
Independence 280
Independent Trials Processes 282
Tree Diagrams 284
Primality Testing 288
Important Concepts，Formulas，and Theorems 289
Problems 290
5.4 Random Variables 292
What Are Random Variables？ 292
Binomial Probabilities 293
A Taste of Generating Functions 295
Expected Value 296
Expected Values of Sums and Numerical Multiples 299
Indicator Random Variables 302
The Number of Trials until the First Success 304
Important Concepts，Formulas，and Theorems 306
Problems 307
5.5 Probability Calculations in Hashing 310
Expected Number of Items per Location 310
Expected Number of Empty Locations 311
Expected Number of Collisions 312
Expected Maximum Number of Elements in a Location of a Hash Table 315
Important Concepts，Formulas，and Theorems 320
Problems 321
5.6 Conditional Expectations，Recurrences，and Algorithms 325
When Running Times Depend on More than Size of Inputs 325
Conditional Expected Values 327
Randomized Algorithms 329
Selection Revisited 331
QuickSort 333
A More Careful Analysis of RandomSelect 336
Important Concepts，Formulas，and Theorems 339
Problems 340
5.7 Probability Distributions and Variance 343
Distributions of Random Variables 343
Variance 346
Important Concepts，Formulas，and Theorems 354
Problems 355
CHAPTER 6 Graphs 359
6.1 Graphs 359
The Degree of a Vertex 363
Connectivity 365
Cycles 367
Trees 368
Other Properties of Trees 368
Important Concepts，Formulas，and Theorems 371
Problems 373
6.2 Spanning Trees and Rooted Trees 375
Spanning Trees 375
Breadth-First Search 377
Rooted Trees 382
Important Concepts，Formulas，and Theorems 386
Problems 387
6.3 Eulerian and Hamiltonian Graphs 389
Eulerian Tours and Trails 389
Finding Eulerian Tours 394
Hamiltonian Paths and Cycles 395
NP-Complete Problems 401
Proving That Problems Are NP-Complete 403
Important Concepts，Formulas，and Theorems 406
Problems 407
6.4 Matching Theory 410
The Idea of a Matching 410
Making Matchings Bigger 414
Matching in Bipartite Graphs 417
Searching for Augmenting Paths in Bipartite Graphs 417
The Augmentation-Cover Algorithm 420
Efficient Algorithms 426
Important Concepts，Formulas，and Theorems 427
Problems 428
6.5 Coloring and Planarity 430
The Idea of Coloring 430
Interval Graphs 433
Planarity 435
The Faces of a Planar Drawing 437
The Five-Color Theorem 441
Important Concepts，Formulas，and Theorems 444
Problems 445
APPENDIX A Derivation of the More General Master Theorem 449
More General Recurrences 449
Recurrences for General n 451
Removing Floors and Ceilings 452
Floors and Ceilings in the Stronger Version of the Master Theorem 453
Proofs of Theorems 453
Important Concepts，Formulas，and Theorems 457
Problems 458
APPENDIX B Answers and Hints to Selected Problems 461
Bibliography 477
Index 479