Topics in Finite and Discrete Mathematics

by Sheldon M. Ross

• ISBN13: 9780521775717
• ISBN10: 052177571X
• Format: Paperback
• Copyright: 2000-07-31
• Publisher: Cambridge University Press

Summary

Written 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 author assumes a level of mathematical sophistication at the beginning calculus level, that is, students should have had at least a course in pre-calculus, and the added sophistication attained from studying calculus would be useful.

Table of Contents

Preface	xi
Preliminaries	1	(33)
Sets	1	(3)
Summation	4	(4)
Mathematical Induction	8	(9)
Functions	17	(6)
The Division Algorithm	23	(5)
Exercises	28	(6)
Combinatorial Analysis	34	(36)
Introduction	34	(1)
The Basic Principle of Counting	34	(2)
Permutations	36	(4)
Combinations	40	(5)
Counting the Number of Solutions	45	(2)
The Inclusion-Exclusion Identity	47	(5)
Using Recursion Equations	52	(9)
The Pigeonhole Principle	61	(2)
Exercises	63	(7)
Probability	70	(27)
Probabilities and Events	70	(4)
Probability Experiments Having Equally Likely Outcomes	74	(3)
Conditional Probability	77	(3)
Computing Probabilities by Conditioning	80	(5)
Random Variables and Expected Values	85	(9)
Exercises	94	(3)
Mathematics of Finance	97	(27)
Interest Rates	97	(3)
Present Value Analysis	100	(4)
Pricing Contracts via Arbitrage	104	(7)
An Example in Options Pricing	104	(3)
Other Examples of Pricing via Arbitrage	107	(4)
The Arbitrage Theorem	111	(5)
The Multiperiod Binomial Model	116	(5)
The Black-Scholes Option Pricing Formula	120	(1)
Exercises	121	(3)
Graphs and Trees	124	(26)
Graphs	124	(3)
Trees	127	(4)
The Minimum Spanning Tree Problem	131	(3)
Cliques and Independent Sets	134	(8)
Euler Graphs	142	(2)
Exercises	144	(6)
Directed Graphs	150	(30)
Directed Graphs	150	(1)
The Maximum Flow Problem	150	(10)
Applications of the Maximum Flow Problem	160	(10)
The Assignment Problem	160	(3)
The Tournament Win Problem	163	(3)
The Transshipment Problem	166	(1)
An Equipment Selection Problem	167	(3)
Shortest Path in Digraphs	170	(5)
Exercises	175	(5)
Linear Programming	180	(23)
The Standard Linear Programming Problem	180	(4)
Transforming to the Standard Form	184	(4)
Minimization and Wrong-Way Inequality Constraints	185	(1)
Problems with Variables Unconstrained in Sign	186	(2)
The Dual Linear Programming Problem	188	(6)
Game Theory	194	(5)
Exercises	199	(4)
Sorting and Searching	203	(17)
Introduction to Sorting	203	(1)
The Bubble Sort	203	(3)
The Quicksort Algorithm	206	(3)
Merge Sorts	209	(1)
Sequential Searching	210	(2)
Binary Searches and Rooted Trees	212	(6)
Exercises	218	(2)
Statistics	220	(17)
Introduction	220	(1)
Frequency Tables and Graphs	220	(3)
Summarizing Data Sets	223	(4)
Sample Mean, Sample Median, and Sample Mode	223	(2)
Sample Variance and Sample Standard Deviation	225	(2)
Chebyshev's Inequality	227	(2)
Paired Data Sets and the Sample Correlation Coefficient	229	(3)
Testing Statistical Hypotheses	232	(1)
Exercises	233	(4)
Groups and Permutations	237	(26)
Permutations and Groups	237	(6)
Permutation Graphs	243	(1)
Subgroups	244	(5)
Lagrange's Theorem	249	(5)
The Alternating Subgroup	254	(5)
Exercises	259	(4)
Index	263