74 3 Probability, Conditional Probability, and Bayes’ Rule
be subtracted. Thus areas of A ∩B, A ∩C, and B ∩C are subtracted from the
sum
P(A)+P(B)+P(C). In this subtraction, the area of A ∩B ∩C is subtracted
three times and should be “patched back.” Alternatively, one can think about
painting the set A
∪B ∪C with a single layer of paint, and the total amount of
paint used is the probability. Of course, the amount of paint needed to paint
the universal event
S is 1. Although very informal, such a discursion can be
quite useful.
3.5 Counting Principles*
Many experiments can be modeled by a sample space with a finite number of
equally likely outcomes. We discussed the experiment of rolling a die, in which
the sample space had six equally likely outcomes. In finding the probability
of an event defined on this sample space we divided the number of outcomes
favorable to A by 6. For example, the event A
={ , , } (the number is even)
has a probability of 3/6=1/2. But what if 10 dice are simultaneously rolled and
we were interested in the probability that the sum of numbers will be equal
to 55? The problem here is to count how many of 6
10
= 60, 466,176 possible
equally likely outcomes produce the sum of 55, and a simple inspection of the
sample space applicable for one or two dice is not feasible. In situations like
this, combinatorial and counting principles help. We will briefly illustrate the
most important principles and introduce mathematical notions (factorial, n-
choose-k, etc.) needed later in the course. A comprehensive coverage and a
wealth of examples can be found in Ross (2009).
We start with definitions and basic properties of factorials and n-choose-k
operations.
Factorial n! is defined as the product
n!
= n(n −1)(n −2)...2 ·1 =
n
Y
i=1
i.
For example, 5!
=5 ·4 ·3 ·2 ·1 =120. By definition 0! =1.
An n-choose-k operation (or binomial coefficient) is defined as follows:
Ã
n
k
!
=
n(n −1) ...(n −k +1)
k!
=
n!
(n −k)!k!
.
As the name indicates, n-choose-k is the number of possible subsets of size k
from a set of n elements. For example, the number of different committees of
size 3 formed from a group of 8 students is
¡
8
3
¢
=
8×7×6
3×2×1
= 56. In MATLAB the
command for
¡
n
k
¢
is nchoosek(n,k). For example, nchoosek(8,3) results in 56.
The following properties follow directly from the definition of
¡
n
k
¢
: