CS 3341 Lecture Notes - Lecture 5: Sample Space, Diddy Kong Racing, Birthday Problem
16 May 2018
School
Department
Course
Professor
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?
