Topics in finite and discrete mathematics

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Preface......Page 13
1.1 Sets......Page 15
1.2 Summation......Page 18
1.3 Mathematical Induction......Page 22
1.4 Functions......Page 31
1.5 The Division Algorithm......Page 37
1.6 Exercises......Page 42
2.2 The Basic Principle of Counting......Page 48
2.3 Permutations......Page 50
2.4 Combinations......Page 54
2.5 Counting the Number of Solutions......Page 59
2.6 The Inclusion–Exclusion Identity......Page 61
2.7 Using Recursion Equations......Page 66
2.8 The Pigeonhole Principle......Page 75
2.9 Exercises......Page 77
3.1 Probabilities and Events......Page 84
3.2 Probability Experiments Having Equally Likely Outcomes......Page 88
3.3 Conditional Probability......Page 91
3.4 Computing Probabilities by Conditioning......Page 94
3.5 Random Variables and Expected Values......Page 99
3.6 Exercises......Page 108
4.1 Interest Rates......Page 111
4.2 Present Value Analysis......Page 114
4.3.1 An Example in Options Pricing......Page 118
4.3.2 Other Examples of Pricing via Arbitrage......Page 121
4.4 The Arbitrage Theorem......Page 125
4.5 The Multiperiod Binomial Model......Page 130
4.5.1 The Black–Scholes Option Pricing Formula......Page 134
4.6 Exercises......Page 135
5.1 Graphs......Page 138
5.2 Trees......Page 141
5.3 The Minimum Spanning Tree Problem......Page 145
5.4 Cliques and Independent Sets......Page 148
5.5 Euler Graphs......Page 156
5.6 Exercises......Page 158
6.2 The Maximum Flow Problem......Page 164
6.3.1 The Assignment Problem......Page 174
6.3.2 The Tournament Win Problem......Page 177
6.3.3 The Transshipment Problem......Page 180
6.3.4 An Equipment Selection Problem......Page 181
6.4 Shortest Path in Digraphs......Page 184
6.5 Exercises......Page 189
7.1 The Standard Linear Programming Problem......Page 194
7.2 Transforming to the Standard Form......Page 198
7.2.1 Minimization and Wrong-Way Inequality Constraints......Page 199
7.2.2 Problems with Variables Unconstrained in Sign......Page 200
7.3 The Dual Linear Programming Problem......Page 202
7.4 Game Theory......Page 208
7.5 Exercises......Page 213
8.2 The Bubble Sort......Page 217
8.3 The Quicksort Algorithm......Page 220
8.4 Merge Sorts......Page 223
8.5 Sequential Searching......Page 224
8.6 Binary Searches and Rooted Trees......Page 226
8.7 Exercises......Page 232
9.2 Frequency Tables and Graphs......Page 234
9.3.1 Sample Mean, Sample Median, and Sample Mode......Page 237
9.3.2 Sample Variance and Sample Standard Deviation......Page 239
9.4 Chebyshev’s Inequality......Page 241
9.5 Paired Data Sets and the Sample Correlation Coefficient......Page 243
9.6 Testing Statistical Hypotheses......Page 246
9.7 Exercises......Page 247
10.1 Permutations and Groups......Page 251
10.2 Permutation Graphs......Page 257
10.3 Subgroups......Page 258
10.4 Lagrange’s Theorem......Page 263
10.5 The Alternating Subgroup......Page 268
10.6 Exercises......Page 273
Index......Page 277