Discrete Mathematics

Contents
1 Introduction 5
2 Let us count! 7
2.1 A party . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Sets and the like . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 The number of subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Induction 21
3.1 The sum of odd numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Subset counting revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Counting regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Counting subsets 27
4.1 The number of ordered subsets . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 The number of subsets of a given size . . . . . . . . . . . . . . . . . . . . . 28
4.3 The Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4 Distributing presents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.5 Anagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.6 Distributing money . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5 Pascal’s Triangle 35
5.1 Identities in the Pascal Triangle . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 A bird’s eye view at the Pascal Triangle . . . . . . . . . . . . . . . . . . . . 38
6 Fibonacci numbers 45
6.1 Fibonacci’s exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.2 Lots of identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.3 A formula for the Fibonacci numbers . . . . . . . . . . . . . . . . . . . . . . 47
7 Combinatorial probability 51
7.1 Events and probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.2 Independent repetition of an experiment . . . . . . . . . . . . . . . . . . . . 52
7.3 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
8 Integers, divisors, and primes 55
8.1 Divisibility of integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
8.2 Primes and their history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
8.3 Factorization into primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
8.4 On the set of primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
8.5 Fermat’s “Little” Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.6 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
8.7 Testing for primality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
9 Graphs 73
9.1 Even and odd degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
9.2 Paths, cycles, and connectivity . . . . . . . . . . . . . . . . . . . . . . . . . 77
10 Trees 81
10.1 How to grow a tree? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
10.2 Rooted trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
10.3 How many trees are there? . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
10.4 How to store a tree? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
11 Finding the optimum 93
11.1 Finding the best tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
11.2 Traveling Salesman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
12 Matchings in graphs 98
12.1 A dancing problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
12.2 Another matching problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
12.3 The main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
12.4 How to find a perfect matching? . . . . . . . . . . . . . . . . . . . . . . . . 104
12.5 Hamiltonian cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
13 Graph coloring 110
13.1 Coloring regions: an easy case . . . . . . . . . . . . . . . . . . . . . . . . . . 110
14 A Connecticut class in King Arthur’s court 114
15 A glimpse of cryptography 117
15.1 Classical cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
16 One-time pads 117
16.1 How to save the last move in chess? . . . . . . . . . . . . . . . . . . . . . . 118
16.2 How to verify a password—without learning it? . . . . . . . . . . . . . . . . 120
16.3 How to find these primes? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
16.4 Public key cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Download this book click here
Another The Core of Computer Science books click here