Summer Mathematics Homepage

Foundations of Mathematics
Summer Program , Columbia University
July 2001 -- Week #4 Notes
Roger B. Blumberg

Session I -- Session II: Review

From Counting to Probabilities

Last week, we learned about permutations and combinations and then tried to generalize the "counting" or "subset making" approach to as many different kinds of problems as we could. Here's another use for the binomial coefficient:

Why? Can we generalize this idea for the equation x[1] + x[2] + .... + x[n] = k ?

Finally, although our discussion of Pascal's Triangle showed how the mathematics of counting can help us identify patterns, you might wonder how the mathematics of combinations can help us with proofs. Here's one example: Prove that the product of any five consecutive integers is divisible by 5! While we could of course prove this by induction, it may be easier to prove it directly:

Take a moment to digest that, think about how we could generalize this to show that the product of any k consecutive integers will be divisible by k!, and then we'll move on to the transition from counting to calculating probabilities.

1. Suppose you are dealt 5 cards from a fair deck of 52. How many different ways are there to get a straight? What is the probability of getting a straight?

The difference between the answer to the first question (C(9,1)*[C(4,1)^5]) and the second question will just be that in the second case we put the answer over C(52,5), which gives the total number of 5 card hands that are possible. This leads to the basic definition of the probability of a discrete event, E,:

(# of successful 
outcomes)/(# of possible outcomes)

2. Suppose that two students are chosen from this class at random. How many different ways might one chose two female students? If the two students are chosen at random, what is the probability that both students are male? That exactly one is male and one is female?

Here again we use binomial coefficients to calculate both the number of successful cases and the total number of possible cases. Thus, if we have a class with 12 females and 8 males, the probability that we have chosen two male students is: C(8,2)/C(20,2).

A. The Concepts of Discrete Probability

We begin by distinguishing elementary, or simple, events from complex events. For example, if we roll a fair die the event "roll a 4" is simple, while the event "roll an odd number" is complex (i.e. made up of more than one simple events). Now, in addition to the basic definition of probability above we have the following fundamental ideas:

B. Repeated trials and the mathematics of counting.

Which of the following strings of coin flips is most likely if the coin is fair?:




Then why, given ten flips of a fair coin, do we think 5H & 5T any more likely than 10H? Given 12 rolls of a fair die, why is 2 of each outcome more likely than 12 fours?

We realize that, for repeated trials, the probability of a complex event will have to take into account both the number of ways the event can occur and the probability of each instance of the event as follows:

p(E) = (# ways E can occur) * (the probability of each instance of E)

We modify the binomial formula to accommodate this insight, by realizing that now each of the "bins" or "subsets" can be represented as having a probability attached to it. Thus, for n repeated flips of a coin, the probability of getting r heads is:

C(n,r) * p(H)^r * p(T)^(n-r)

We can also modify the multinomial formula, and find that for n repeated rolls of a die, the probability of getting exactly: r(1) 1s; r(2) 2s; r(3) 3s; r(4) 4s; r(5) 5s; and r(6) 6s is:

C(n,r1,r2,..r6) * p(1)^r1 * p(2)^r2 * ... * 

For example, suppose we go back to the insects we were talking about at the start of the unit on counting. Suppose we have 20 ants, 30 bees and 50 roaches all in one box, and we choose 10 insects at random (all at once). What is the probability we choose 2 ants, 3 bees, and 5 roaches? Before calculating, do you think the probability greater than .5? Do you think this outcome the most likely to occur? How can you reconcile the small probability with the fact that it is the most likely outcome?

We now have a mathematical theory of probability which incorporates our theories about counting.

C. Conditional Probability and Bayes Theorem

Recognizing the importance of the outcome space in all of our calculations, it is easy to understand why having information restricts the outcome space allows us to make more accurate probability judgements. Consider how your answers would differ in the following cases:

  1. Two fair dice are rolled. What is the probability that the outcome is double sixes?

  2. Two fair dice are rolled and the outcome is divisible by 3. What is the probability that the outcome is double sixes?

Clearly the outcome space is more restricted in the second case, and thus our answer in the second case is different than in the first. (Aside: can you think of a piece of information that would have made us judge the possibility lower in the second case?)

We can use this example to derive a formula for conditional probability:

p(A|B) = p(A and B) / p(B)

Finally, we can build on this idea and come up with a method for dealing with cases in which a particular event can occur in any of several subsets. For example, consider a high school population in which some of the members of each grade are smokers. Suppose we want to figure out the probability of choosing a smoker if we randomly choose a student from the school.

Bayes Theorem states that if a finite outcome space is completely divided into disjoint subsets (e.g. s[1], s[2], s[3], ..., s[n]), then for any event, E, in the outcome space:

p(E) = p(E|s[1])*p(s[1]) + p(E|s[2])*p(s[2]) + ...... + p(E|s[n])*p(s[n])


A. In order to review the basic of probability from last time, and the way the counting methods we studied last week are integrated into combinatorial probability we look at four problems:

  1. A fair die is rolled. What is the probability of getting a 4? an even number?
  2. Two fair dice are rolled. What is p(sum=5)? p(the products of the dies is prime)?
  3. A fair die is rolled 7 times. What is p(exactly three 4s)?
  4. If a fair die is rolled sixty times, which has the greater probability: p(thirty 3s) or p(ten 3s)?

B. In preparation for the final exam, in past years I've solicited questions from students. Here are some of the kinds of questions that were asked.

Now to the final exam.

Summer Mathematics Homepage Summer Mathematics Reference Page
© 2001 Roger B. Blumberg