book

Concrete Mathematics: A Foundation for Computer Science, 2nd Edition

by Ronald L. Graham, Donald E. Knuth, Oren Patashnik

February 1994

Intermediate to advanced

672 pages

18h 51m

English

Addison-Wesley Professional

Read now

Unlock full access

1.1 The Tower of Hanoi1.2 Lines in the Plane1.3 The Josephus ProblemExercises

2.1 Notation2.2 Sums and Recurrences2.3 Manipulation of Sums2.4 Multiple Sums2.5 General Methods2.6 Finite and Infinite Calculus2.7 Infinite SumsExercises
3.1 Floors and Ceilings3.2 Floor/Ceiling Applications3.3 Floor/Ceiling Recurrences3.4 ‘MOD’: The Binary Operation3.5 Floor/Ceiling SumsExercises
4.1 Divisibility4.2 Primes4.3 Prime Examples4.4 Factorial Factors4.5 Relative Primality4.6 ‘MOD’: The Congruence Relation4.7 Independent Residues4.8 Additional Applications4.9 PHI and MUExercises
5.1 Basic Identities5.2 Basic Practice5.3 Tricks of the Trade5.4 Generating Functions5.5 Hypergeometric Functions5.6 Hypergeometric Transformations5.7 Partial Hypergeometric Sums5.8 Mechanical SummationExercises
6.1 Stirling Numbers6.2 Eulerian Numbers6.3 Harmonic Numbers6.4 Harmonic Summation6.5 Bernoulli Numbers6.6 Fibonacci Numbers6.7 ContinuantsExercises
7.1 Domino Theory and Change7.2 Basic Maneuvers7.3 Solving Recurrences7.4 Special Generating Functions7.5 Convolutions7.6 Exponential gf’s7.7 Dirichlet Generating FunctionsExercises
8.1 Definitions8.2 Mean and Variance8.3 Probability Generating Functions8.4 Flipping Coins8.5 HashingExercises
9.1 A Hierarchy9.2 O Notation9.3 O Manipulation9.4 Two Asymptotic Tricks9.5 Euler’s Summation Formula9.6 Final SummationsExercises

Content preview from Concrete Mathematics: A Foundation for Computer Science, 2nd Edition

8 Discrete Probability

The element of chance enters into many of our attempts to understand the world we live in. A mathematical theory of probability allows us to calculate the likelihood of complex events if we assume that the events are governed by appropriate axioms. This theory has significant applications in all branches of science, and it has strong connections with the techniques we have studied in previous chapters.

Probabilities are called “discrete” if we can compute the probabilities of all events by summation instead of by integration. We are getting pretty good at sums, so it should come as no great surprise that we are ready to apply our knowledge to some interesting calculations of probabilities and averages.