Acknowledgements......Page 7
Preface......Page 9
How to use this book......Page 11
What is Discrete Mathematics?......Page 17
Atomic and Molecular Statements......Page 20
Implications......Page 23
Predicates and Quantifiers......Page 31
Exercises......Page 33
Notation......Page 40
Relationships Between Sets......Page 44
Operations On Sets......Page 47
Venn Diagrams......Page 49
Exercises......Page 51
Functions......Page 55
Describing Functions......Page 56
Surjections, Injections, and Bijections......Page 61
Image and Inverse Image......Page 64
Exercises......Page 67
Additive and Multiplicative Principles......Page 73
Counting With Sets......Page 77
Principle of Inclusion/Exclusion......Page 80
Exercises......Page 83
Subsets......Page 86
Bit Strings......Page 88
Lattice Paths......Page 89
Binomial Coefficients......Page 90
Pascal's Triangle......Page 93
Exercises......Page 94
Combinations and Permutations......Page 97
Exercises......Page 102
Patterns in Pascal's Triangle......Page 105
More Proofs......Page 111
Exercises......Page 115
Stars and Bars......Page 119
Exercises......Page 124
Advanced Counting Using PIE......Page 127
Counting Derangements......Page 131
Counting Functions......Page 133
Exercises......Page 140
Chapter Summary......Page 143
Chapter Review......Page 144
Sequences......Page 151
Describing Sequences......Page 152
Exercises......Page 160
Arithmetic and Geometric Sequences......Page 164
Sums of Arithmetic and Geometric Sequences......Page 167
Exercises......Page 172
Polynomial Fitting......Page 176
Exercises......Page 180
Solving Recurrence Relations......Page 183
The Characteristic Root Technique......Page 187
Exercises......Page 191
Stamps......Page 193
Formalizing Proofs......Page 195
Examples......Page 197
Strong Induction......Page 201
Exercises......Page 204
Chapter Summary......Page 209
Chapter Review......Page 210
Symbolic Logic and Proofs......Page 213
Propositional Logic......Page 214
Truth Tables......Page 215
Logical Equivalence......Page 217
Deductions......Page 220
Beyond Propositions......Page 223
Exercises......Page 225
Proofs......Page 229
Direct Proof......Page 231
Proof by Contrapositive......Page 232
Proof by Contradiction......Page 234
Proof by (counter) Example......Page 236
Proof by Cases......Page 237
Exercises......Page 239
Chapter Summary......Page 243
Chapter Review......Page 244
Graph Theory......Page 247
Definitions......Page 249
Exercises......Page 259
Trees......Page 263
Properties of Trees......Page 264
Rooted Trees......Page 267
Spanning Trees......Page 269
Exercises......Page 271
Planar Graphs......Page 274
Non-planar Graphs......Page 276
Polyhedra......Page 278
Exercises......Page 281
Coloring......Page 283
Coloring in General......Page 285
Coloring Edges......Page 288
Exercises......Page 290
Euler Paths and Circuits......Page 293
Hamilton Paths......Page 295
Exercises......Page 296
Matching in Bipartite Graphs......Page 299
Exercises......Page 302
Chapter Summary......Page 305
Chapter Review......Page 306
Generating Functions......Page 311
Building Generating Functions......Page 312
Differencing......Page 315
Multiplication and Partial Sums......Page 317
Solving Recurrence Relations with Generating Functions......Page 318
Exercises......Page 320
Divisibility......Page 323
Remainder Classes......Page 326
Properties of Congruence......Page 329
Solving Congruences......Page 333
Solving Linear Diophantine Equations......Page 335
Exercises......Page 339
Selected Hints......Page 341
Selected Solutions......Page 351
List of Symbols......Page 403
Index......Page 405