Discrete Mathematics: An Introduction to Proofs and Combinatorics

Front Cover......Page 1
Title Page......Page 2
Copyright......Page 3
Contents......Page 4
Preface......Page 6
Acknowledgments......Page 9
Base s......Page 10
Binary (Base Two)......Page 11
Expressing Numbers in Alternative Bases......Page 12
Octal (Base Eight) and Hexadecimal (Base Sixteen)......Page 13
Other Bases......Page 14
Questions for Thought......Page 15
Part I: Proofs......Page 16
1.1 Statement Forms and Logical Equivalences......Page 18
1.2 Set Notation......Page 32
1.3 Quantifiers......Page 41
1.4 Set Operations and Identities......Page 51
1.5 Valid Arguments......Page 63
CHAPTER 1 Review Problems......Page 74
2.1 Direct Demonstration......Page 78
2.2 General Demonstration (Part 1)......Page 84
2.3 General Demonstration (Part 2)......Page 91
2.4 Indirect Arguments......Page 97
2.5 Splitting into Cases......Page 103
CHAPTER 2 Review Problems......Page 109
3.1 Divisors......Page 112
3.2 Consequences of Well-Ordering......Page 122
3.3 Euclid\'s Algorithm and Lemma......Page 139
3.4 Rational Numbers......Page 145
3.5 Irrational Numbers......Page 151
3.6 Modular Arithmetic......Page 159
CHAPTER 3 Review Problems......Page 171
4.1 Sequences, Indexing, and Recursion......Page 176
4.2 Sigma Notation......Page 186
4.3 Mathematical Induction, an Introduction......Page 194
4.4 Induction and Summations......Page 204
4.5 Strong Induction......Page 210
4.6 The Binomial Theorem......Page 220
CHAPTER 4 Review Problems......Page 227
5.1 General Relations......Page 231
5.2 Special Relations on Sets......Page 244
5.3 Basics of Functions......Page 259
5.4 Special Functions......Page 270
5.5 General Set Constructions......Page 284
5.6 Cardinality......Page 295
CHAPTER 5 Review Problems......Page 304
Part II: Combinatorics......Page 310
6.1 The Multiplication Principle......Page 312
6.2 Permutations and Combinations......Page 320
6.3 Addition and Subtraction......Page 329
6.4 Probability......Page 337
6.5 Applications of Combinations......Page 350
6.6 Correcting for Overcounting......Page 360
CHAPTER 6 Review Problems......Page 367
7.1 Inclusion-Exclusion......Page 373
7.2 Multinomial Coefficients......Page 382
7.3 Generating Functions......Page 390
7.4 Counting Orbits......Page 399
7.5 Combinatorial Arguments......Page 412
CHAPTER 7 Review Problems......Page 420
8.1 Motivation and Introduction......Page 424
8.2 Matrices and Special Graphs......Page 438
8.3 Isomorphisms......Page 455
8.4 Invariants......Page 467
8.5 Directed Graphs and Markov Chains......Page 480
CHAPTER 8 Review Problems......Page 499
9.1 Connectivity......Page 506
9.2 Euler Circuits......Page 516
9.3 Hamiltonian Cycles......Page 525
9.4 Planar Graphs......Page 536
9.5 Chromatic Number......Page 547
CHAPTER 9 Review Problems......Page 561
10.1 Trees......Page 568
10.2 Search Trees......Page 583
10.3 Weighted Trees......Page 596
10.4 Analysis of Algorithms (Part 1)......Page 609
10.5 Analysis of Algorithms (Part 2)......Page 620
CHAPTER 10 Review Problems......Page 630
APPENDIX A: Assumed Properties of Z and R......Page 636
APPENDIX B: Pseudocode......Page 639
Answers to Selected Exercises......Page 642
Bibliography......Page 706
Index......Page 708