Transcript No Slide Title

Counting and
Probability
•Sets and Counting
•Permutations & Combinations
•Probability
Sets and Counting
A set is a well-defined collection of
distinct objects.
Well-defined means there is a rule that
enables us to determine whether a given
object is an element of the set.
If a set has no elements, it is called
the empty set, or null set, and is
denoted by the symbol .
If two sets A and B have precisely the same
elements, then A and B are said to be
equal and write A = B.
If each element of a set A is also an element of
a set B, then we say that A is a subset of B and
write A  B
If A  B and A  B, then we say that A is a
proper subset of B and write A  B.
  A for any set A
Write down all subsets of  x , y , z.
0 elements: 
1 element:  x,  y, z
2 elements:  x , y,  x , z,  y , z
3 elements:  x , y , z
If A and B are sets, the intersection of A with B,
denoted, A  B, is the set consisting of elements
that belong to both A and B. The union of A
with B, denoted A  B, is the set consisting of
elements that belong to either A or B, or both.
Designate the universal set, denoted U ,
as the set consisting of all the elements
we wish to consider.
If A is a set, the complement of A, denoted A,
is the set consisting of all the elements in the
universal set not in A.
A
U
B
A B
A
B
U
A B  
A
B
U
A B
B
A
U
A B
A
A
U
A
U  blue, red, green, yellow, orange
A  blue, red B  blue, green, orange
Find
(a) A  B
(b) A  B (c) A
(a) A  B  blue, red, green, orange
(b) A  B  blue
(c) A  green, yellow, orange
Theorem: Counting Formula
If A and B are finite sets, then
n A  B  n A  n B  n A  B
In survey of 50 people, 21 said they owned
stocks, 32 said they owned bonds and 12 said
they owned both stocks and bonds. How
many of the 50 people owned stocks or
bonds? How many owned neither?
A: person owns stock B: person owns bonds
n( A  B)  n( A)  n( B)  n( A  B)
= 21 + 32 - 12 = 41
50 - 41 = 9 owned neither
Universe is 50 people.
In A = 21 owned stocks.
In B = 32 owned bonds.
In AB = 12 owned both stocks and bonds.
In AB = 53-12 = 41 owned stocks or
bonds.
In (AB)= 50-41 = 9
owned neither.
A
21
AB
_12
B
32
(AB)
_ _9
Permutations and Combinations
This is a tricky subject where even the
text author makes mistakes. The next
three slides are to distinguish some of
the subtleties. After these are the slides
from the text set and that help to
elaborate some cases. Some situations
can be very difficult to evaluate.
Counting Permutation Cases I
A permutation is an ordered arrangement of r
objects from n objects. To find the total number of
possible cases, the easy types of situations are:
1. Multiplication of p,q,r,s, ... ways of selection =>
Total number of cases is N = p•q•r•s•...
2. The number of permutations of r distinct
objects with allowed repetition from n distinct
objects (order is important) => N = nr
3. The number of permutations of r distinct
objects with no repetition from n distinct objects
(order is important) => N = P(n, r) = n!/(n - r)!
Counting Permutation Cases II
A permutation is an ordered arrangement of r
objects from n objects.
An important harder situation of finding the total
number of possible cases is when there are k
distinct types each of non-distinct objects, with
n1 of the 1st type, n2 of the 2nd type, ... nk of the
kth type, and n = n1 + n2 + n3 + ... nk.
4. Permutation of n, some non-distinct, objects
with allowed repetition from k distinct types of
objects (order is important) =>
N = n!/[n1! • n2! ... • nk!].
Counting Combination Cases
A combination is an arrangement with no
regard to order of r distinct objects without
repetition from n distinct objects (r < n). For
finding the total number of possible cases,
the easy type of situation is:
The number of combinations of r distinct
objects without repetition from n distinct
objects (order is not important) =>
N = C(n, r) = n!/[r!(n - r)!].
Permutations and Combinations
Theorem: Multiplication Principle of Counting
If a task consists of a sequence of choices in
which there are p selections for the first
choice, q selections for the second choice, r
selections for the third choice, and so on,
then the task of making these selections can
be done in
p  q  r
different ways.
If a license plate consists of a letter,
then 5 numbers, how many different
types of license plates are possible?
26  10  10  10  10  10  2,600,000 license plates
A permutation is an ordered
arrangement of n distinct objects
without repetitions. The symbol
P(n, r) represents the number of
permutations of n distinct objects,
taken r at a time, where r < n.
Theorem: Number of Permutations of n
Distinct Objects Taken r at a Time
The number of different arrangements from
selecting r objects from a set of n objects (r < n),
in which
1. the n objects are distinct
2. once an object is used, it cannot be repeated
3. order is important
is given by the formula
n!
P ( n, r ) 
(n  r )!
Evaluate: P(10, 3)
10!
10!
P(10, 3) 

(10  3)! 7!
10  9  8  7!

7!
 720
A combination is an arrangement,
without regard to order, of n distinct
objects without repetitions. The symbol
C(n, r) represents the number of
combinations of n distinct objects taken
r at a time, where r < n.
Theorem: Number of Combinations of n
Distinct Objects Taken r at a Time
The number of different arrangements from
selecting r objects from a set of n objects (r < n),
in which
1. the n objects are distinct
2. once an object is used, it cannot be repeated
3. order is not important
is given by the formula
 n
n!
C (n, r )  n C r    
.
r!(n  r )!
r
Evaluate: C(10, 3)
10!
10!
C(10, 3) 

3!(10  3)! 3!7!
10  9  8  7! 10  9  8


3!7!
3 2 1
 120
Probability
An event is an outcome from an experiment.
Its probability gives the likelihood it occurs.
A probability model lists the different
outcomes from an experiment and their
corresponding probabilities.
To construct probability models, we need to
know the sample space of the experiment.
This is the set S that lists all the possible
outcomes of the experiment.
Determine the sample space resulting
from the experiment of rolling a die.
S = {1, 2, 3, 4, 5, 6}
Properties of Probabilities
For a sample space S  e1 , e2 ,en 
1. 0  P(ei )  1 for all events ei
n
2.  P(ei )  P(e1 )  P(e2 )  P(en )
i 1
=1
Determine which of the following are
probability models from rolling a single die.
Outcome Probability
1
0.3
2
0.1
3
0.05
4
0.2
5
0.15
6
0.25
Not a probability model. The sum of all
probabilities is not 1.
Outcome
1
2
3
4
5
6
Probability
0.2
0.2
0.2
0.2
0.2
0
All probabilities between 0 and 1
inclusive and the sum of all probabilities
is 1.
Outcome
1
2
3
4
5
6
Probability
0.25
0.1
0.35
0.15
0.2
-0.05
Not a probability model. The event “roll a 6”
has a negative probability.
Theorem: Probability for Equally Likely
Outcomes
If an experiment has n equally likely
outcomes, and if the number of ways an
event E can occur is m, then the probability
of E is
Number of ways that E can occur m
P( E ) 

Total number of possible outcomes n
A classroom contains 20 students: 7
Freshman, 5 Sophomores, 6 Juniors, and 2
Seniors. A student is selected at random.
Construct a probability model for this
experiment.
7
P( F ) 
20
6
P( Jr ) 
20
5
P( Soph) 
20
2
P( Sr ) 
20
Theorem: Additive Rule of P(E  F)
For any two events E and F
P( E  F )  P( E )  P( F )  P( E  F )
P( E  F )  P( E )  P( F )
if E and F are mutually exclusive.
What is the probability of selecting an Ace
or Diamond from a standard deck of cards?
4
1
P(Ace) = 
52 13
13 1
P( Diamond) = 
52 4
P(Ace or Diamond)
= P(Ace) + P(Diamond) - P(Ace and Diamond)
1 1 1 16 4
 
  
13 4 52 52 13
Let S denote the sample space of an
experiment and let E denote an event.
The complement of E, denoted E, is
the set of all outcomes in the sample
space S that are not outcomes in the
event E.
Theorem: Computing Probabilities of
Complementary Events
If E represents any event and E represents the
complement of E, then
P( E )  1  P( E )
The probability of having 4 boys in a four
child family is 0.0625. What is the probability
of having at least one girl?
Sample Space: {4 boys; 3 boys, 1 girl, 2
boys, 2 girls; 1 boy, 3 girls; 4 girls}
E = “at least one girl”
E = “4 boys”
P(E) = 1 - P(E) = 1 - 0.0625 = 0.9375
What is the probability of obtaining 3 of
a kind when 5 cards are drawn from a
standard 52-card deck?
C (4,3)  48  44
P(3 of a kind) 
C (52,5)
 0.00325  0.325%
This answer from the text slides is just wrong. For the correct
value of 2.11% and similar examples see either of the poker sites:
http://www.math.sfu.ca/~alspach/comp18/
http://www.pvv.ntnu.no/~nsaa/poker.html
What is the probability of obtaining 3 of
a kind when 5 cards are drawn from a
standard 52-card deck?
Done correctly, one has
13  4  C (12,2)  4  4
P(3 of a kind) 
C (52,5)
54,912
 0.0211  2.11%

2,598,960
Why?