## Topics in Finite and Discrete MathematicsWritten for a broad audience of students in mathematics, computer science, operations research, statistics, and engineering, this textbook presents a short, lively survey of several fascinating non-calculus topics in modern applied mathematics. Coverage includes probability, mathematical finance, graphs, linear programming, statistics, computer science algorithms, and groups. A key feature is the abundance of interesting examples not normally found in standard finite mathematics courses, such as options pricing and arbitrage, tournaments, and counting formulas. The only prerequisite is a course in pre-calculus, although the added sophistication attained from studying calculus would be useful. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Preliminaries | 1 |

12 Summation | 4 |

13 Mathematical Induction | 8 |

14 Functions | 17 |

15 The Division Algorithm | 23 |

16 Exercises | 28 |

Combinatorial Analysis | 34 |

23 Permutations | 36 |

63 Applications of the Maximum Flow Problem | 160 |

632 The Tournament Win Problem | 163 |

633 The Transshipment Problem | 166 |

634 An Equipment Selection Problem | 167 |

64 Shortest Path in Digraphs | 170 |

65 Exercises | 175 |

Linear Programming | 180 |

72 Transforming to the Standard Form | 184 |

24 Combinations | 40 |

25 Counting the Number of Solutions | 45 |

26 The InclusionExclusion Identity | 47 |

27 Using Recursion Equations | 52 |

28 The Pigeonhole Principle | 61 |

29 Exercises | 63 |

Probability | 70 |

32 Probability Experiments Having Equally Likely Outcomes | 74 |

33 Conditional Probability | 77 |

34 Computing Probabilities by Conditioning | 80 |

35 Random Variables and Expected Values | 85 |

36 Exercises | 94 |

Mathematics of Finance | 97 |

42 Present Value Analysis | 100 |

43 Pricing Contracts via Arbitrage | 104 |

432 Other Examples of Pricing via Arbitrage | 107 |

44 The Arbitrage Theorem | 111 |

45 The Multiperiod Binomial Model | 116 |

451 The BlackScholes Option Pricing Formula | 120 |

46 Exercises | 121 |

Graphs and Trees | 124 |

52 Trees | 127 |

53 The Minimum Spanning Tree Problem | 131 |

54 Cliques and Independent Sets | 134 |

55 Euler Graphs | 142 |

56 Exercises | 144 |

Directed Graphs | 150 |

721 Minimization and WrongWay Inequality Constraints | 185 |

722 Problems with Variables Unconstrained in Sign | 186 |

73 The Dual Linear Programming Problem | 188 |

74 Game Theory | 194 |

75 Exercises | 199 |

Sorting and Searching | 203 |

83 The Quicksort Algorithm | 206 |

84 Merge Sorts | 209 |

85 Sequential Searching | 210 |

86 Binary Searches and Rooted Trees | 212 |

87 Exercises | 218 |

Statistics | 220 |

93 Summarizing Data Sets | 223 |

932 Sample Variance and Sample Standard Deviation | 225 |

94 Chebyshevs Inequality | 227 |

95 Paired Data Sets and the Sample Correlation Coefficient | 229 |

96 Testing Statistical Hypotheses | 232 |

97 Exercises | 233 |

Groups and Permutations | 237 |

102 Permutation Graphs | 243 |

103 Subgroups | 244 |

104 Lagranges Theorem | 249 |

105 The Alternating Subgroup | 254 |

106 Exercises | 259 |

263 | |

### Other editions - View all

### Common terms and phrases

algorithm amount arbitrage arbitrage theorem balls beads betting strategy binomial bubble sort called choose consider constraints contain Corollary cost cycle data set data values defined denote the number determine digraph directed graph divisor dual edge capacities equal equation equivalent event Example Exercise experiment Figure Find finite follows function Hence identity implies induction hypothesis instance integer interest rate inversions investment Lagrange's theorem least Lemma mathematical induction max-flow min-cut theorem maximal maximum flow problem minimal nonnegative normal subgroup number of comparisons number of different number of edges number of elements obtain option path permanently labeled pigeonhole principle player positive integer possible outcomes preceding probability vector Proof Proposition prove purchase quicksort random variable result rooted tree s-t cut sample correlation coefficient sample mean sample space sequence smallest Solution standard linear program subgroup subsets Suppose vertex