Discrete Mathematics. An open Introduction

Description

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