CS 3341 Lecture Notes - Lecture 5: Sample Space, Diddy Kong Racing, Birthday Problem
Section 2.3 Combinatorics
Page 1 of 8
“I present here without the aid of analysis the principles and general results of this
theory [probability], applying them to the most important questions of life, which are
indeed for the most part only problems of probability.”
—Pierre Simon, marquis de Laplace, from A Philosophical Essay on Probabilities
Equally likely outcomes
When the sample space consists of equally likely outcomes, we
compute the probability of an event as
“The theory of chance consists in reducing all the events of the same kind to a certain number of cases
equally possible…and in determining the number of cases favorable to the event whose probability is
sought. The ratio of this number to that of all the cases possible is the measure of this probability, which
is thus simply a fraction whose numerator is the number of favorable cases and whose denominator is
the number of all the cases possible.”
—Ibid.
Outcomes in are traditionally called “favorable,” so we may write
Example: An urn contains 3 red marbles and 5 blue marbles, and a marble is drawn at
random. Let be the event of “drawing a red marble.” Identify so that it consists of
equally likely outcomes and compute .
Example: If a family has two children, what is the probability of having two boys?
Section 2.3 Combinatorics
Page 2 of 8
Sampling, permutations, and combinations
and
are not always simple to compute. When a situation involves selecting
objects at random from a set of objects, we may use combinatorics to compute
and
.
We will look at experiments where objects are sampled, or randomly selected, at a
time.
Objects may be sampled with or without replacement, and with or without
distinguishing different orders.
With Replacement
Every sampled object is replaced, so at any time the probability of selecting any
individual object is .
Without Replacement
Every sampled object is removed and will not be sampled again, so the set of
possibilities reduces by 1 after each selection.
Distinguishable (or, “order matters”)
The exact same objects sampled in a different order is considered a different outcome.
In particular, when a hierarchy or ranking is given to the sampled objects, the order is
distinguished.
Indistinguishable (or, “order does not matter”)
The order is not important, only which objects were sampled and which were not.
Section 2.3 Combinatorics
Page 3 of 8
Example: A randomly generated password.
is…
is…
Replacement?
Order?
Example: A random selection of students from a class for a poll.
is…
is…
Replacement?
Order?