Transcript 5.5 - MAT143

5.5
Counting Techniques
More Challenging Stuff
 The
classical method, when all
outcomes are equally likely, involves
counting the number of ways
something can occur
 This section includes techniques for
counting the number of results in a
series of choices, under several
different scenarios
Example
●
●
●
If there are 3 different colors of
paint (red, blue, green) that can be
used to paint 2 different types of toy
cars (race car, police car), then
how many different toys can there
be?
3 colors … 2 cars … 3 • 2 = 6
different toys
This can be shown in a table or in a
tree diagram
Table
A
table of the different possibilities
 This
is a rectangle with 2 rows and 3
columns … 2 • 3 = 6 entries
Tree Diagram
A
tree diagram of the different
possibilities
Car
Paint
Red
Blue
Green
Race
Red Race Car
Police
Red Police Car
Race
Blue Race Car
Police
Blue Police Car
Race
Green Race Car
Police
Green Police Car
Multiplication Rule of Counting
 The
Multiplication Rule of Counting
applies to this type of situation
 If a task consists of a sequence of
choices
 With
p selections for the first choice
 With q selections for the second choice
 With r selections for the third choice
…
Then the number of different tasks is
p•q•r•…
Example
Example Part A
● A child is coloring a picture of a shirt
and pants
● There are 5 different colors of
markers
● How many ways can this be
colored?
● By the multiplication rule
5 • 5 = 25
●
Different Example
Example Part B
● A child is coloring a picture of a shirt and
pants
● There are 5 different colors of markers
● The child wants to use 2 different colors
● How many ways can this be colored?
● By the multiplication rule
5 • 4 = 20
●
Example continued
Allowing the same marker to be used twice
5 • 5 = 25
● Requiring that there be two different markers
5 • 4 = 20
● There are 5 selections for the first choice for
both Part A and Part B of this example
● But they differ for the second choice … there
are only 4 selections for Part B
●
Repetition??
Example continued
● Part A, allowing the same marker to be
used twice, is called counting with
repetition and has formulas such as
5•5•5•…
● Part B, requiring that there be two different
markers, is called counting without
repetition and has formulas such as
5•4•3•…
●
Calculator Commands
 While
in a
CALCULATOR
Page:
 Menu,
Probability,
 We will be using
Factorial,
permutations, &
combinations
Factorial
One way to help write these products is using the
factorial symbol n!
n! = n • (n-1) • (n-2) • … • 2 • 1
● We start off by saying that
0! = 1 and 1! = 1
● For example
5! = 5 • 4 • 3 • 2 • 1 = 120
● Notice how 5! looks like the 5 • 4 • 3 from the
previous example
●
Permutation (Order Matters)
●
●
The problem of choosing one marker out
of 5 and then choosing a second marker
out of the 4 remaining is an example of a
permutation
A permutation is an




●
ordered arrangement, in which
r different objects are chosen out of
n different objects with
repetition not allowed
The number of ways is written nPr
Permutation Formula
A
mathematical way to write the formula for the
number of permutations is
 This
is a very convenient mathematical way to
write a formula for nPr, but it is not a particularly
efficient way to actually compute it
 In particular, n! gets rapidly gets very large
Order
●
●
For some problems, the order of choice
does not matter
Order matters example


●
Choosing one person to be the president of a
club and another to be the vice-president
Two different roles
Order does not matter example


Choosing two people to go to a meeting
The same role
Combination (Order Does Not
Matter)
●
●
When order does not matter, this is
called a combination
A combination is an




●
unordered arrangement, in which
r different objects are chosen out of
n different objects with
repetition not allowed
The number of ways is written nCr
Permutation vs. Combination
 Comparing
the description of a permutation
with the description of a combination
 The
only difference is whether order matters
Combination Formula
 Because
each combination corresponds
to r! permutations, the formula nCr for the
number of combinations is
Example
●
If there are 8 researchers and 3 of them are to
be chosen to go to a meeting
A combination since order does not matter
●
There are 56 different ways that this can be done
●
Permutation or Combination
●
●
Is a problem a permutation or a
combination?
One way to tell


●
Write down one possible solution (i.e. Roger, Rick,
Randy)
Switch the order of two of the elements (i.e. Rick,
Roger, Randy)
Is this the same result?


If no – this is a permutation – order matters
If yes – this is a combination – order does not matter
Different
 Our
permutation and combination
problems so far assume that all n total
items are different
 Sometimes we have a permutations but
not all of the n items are different
 This is a more complicated problem
 How many ways are there?
Example
●
How many ways to put 3 A’s, 2 N’s, and 2
T’s to try to make a seven letter
sequence?
____ ____ ____ ____ ____ ____ ____
● Each of the blanks can be filled in with
either an A or a N or a T
● The three A’s are the same … the two N’s
are the same … the two T’s are the same
Example Continued
Where
 There
can the A’s go?
are 7 possible places
 Any 3 of them are possible
 Order does not matter
 So 7C3 different ways to put in the A’s
Example Continued
 Where
can the N’s go?
 There
are 4 possible places (since 3 of the 7
have been taken by the A’s already)
 Any 2 of them are possible
 Order does not matter
 So 4C2 different ways to put in the N’s
 And
there are 2C2 different ways to put in
the T’s
Example Continued
Altogether there are
7C 3 • 4C2 • 2C2
different ways
● This is
●
●
Notice that the denominator is 3, 2, 2 … the
numbers of each letter
Permutation
●
●
●
●
A permutation example
In a horse racing “Trifecta”, a gambler
must pick which horse comes in first, which
second, and which third
If there are 8 horses in the race, and every
order of finish is equally likely, what is the
chance that any ticket is a winning ticket?
Order matters, so this is a permutations
problem
Permutation Cont.
A
permutation example continued
 There are 8P3 permutations of the
order of finish of the horses
 The probability that any one ticket is
a winning ticket is 1 out of 8P3, or 1
out of 336
Combination Example
●
●
●
●
●
A combination example
The Powerball lottery consists of choosing 5
numbers out of 55 and then 1 number out of
42
The grand prize is given out when all 6
numbers are correct
What is the chance of getting the grand
prize?
Order does not matter, so this is a
combinations problem (for the 5 balls)
Combination Cont.
●
●
●
A combination example continued
There are 55C5 combinations of the 5 numbers
There are 42 possibilities for the last ball, so the
probability of the grand prize is 1 out of
which is pretty small
Summary
 The
Multiplication Rule counts the
number of possible sequences of items
 Permutations and combinations count
the number of ways of arranging items,
with permutations when the order
matters and combinations when the
order does not matter
 Permutations and combinations are used
to compute probabilities in the classical
method