Transcript 3.4 Counting Principles

3.4 Counting Principles
Statistics
Mrs. Spitz
Fall 2008
Objectives/Assignment
• How to use the Fundamental Counting Principle
to find the number of ways two or more events
can occur.
• How to find the number of ways a group of
objects can be arranged in order.
• How to find the number of ways to choose
several objects from a group without regard to
order.
• How to use counting principles to find
probabilities
• Assignment: pp. 140-142 #1-30 all
The Fundamental Counting
Principle
• If one event can occur in m ways and
a second event can occur in n ways,
the number of ways the two events
can occur in sequence is m ● n. This
rule can be extended for any number
of events occurring in sequence.
Example 1
• You are purchasing a new car. Using the
following manufacturers, car sizes and
colors, how many different ways can you
select one manufacturer, one car size and
one color?
Manufacturer: Ford, GM, Chrysler
Car size: small, medium
Color: white(W), red(R), black(B), green(G)
Solution
• There are three choices of manufacturer,
two choices of car sizes, and four colors.
So, the number of ways to select one
manufacturer, one car size and one color
is:
3 ●2●4 = 24 ways. A tree diagram can
help you see why there are 24 options.
Tree diagram for Car Selections
Ford
Chrysler
GM
Medium
w
w
w
w
w
w
R
R
R
R
R
R
B
B
B
B
B
B
G
G
G
G
G
G
Do you see now?
Small
Medium
Small Medium
Small
Ex. 2 Using the Fundamental Counting
Principle
• The access code for a car’s security
system consists of four digits. Each
digit can be 0 through 9. How many
access codes are possible if:
1. each digit can be used only once
and not repeated?
2. each digit can be repeated?
Solution to 1
1. each digit can be used only once and not
repeated?
Because each digit can only be used once,
there are 10 choices for the first digit, 9
digits for the second, 8 choices left for the
3rd digit, and 7 for the fourth digit. Using
the fundamental counting principle, you
could conclude there are:
10●9●8●7 = 5040 possible access codes.
Solution to 2
2. Each digit can be repeated.
Because each digit can be repeated,
there are 10 choices for each of the
four digits, So there are:
10●10●10●10 = 10,000 possible
access codes.
Permutations
• An important application of the
Fundamental Counting Principle is
determining the number of ways that n
objects can be arranged in order or in a
permutation.
• Definition of permutation: An ordered
arrangement of objects. The number of
different permutations of n distinct objects
is n!.
Permutations
• The expression n! is read as n
factorial and is defined as follows:
n! = n ●(n -1)●(n -2)●(n-3) ● ● ● 3 ● 2 ● 1
As a special case, 0! = 1
Study Tip
Here are several values of n!.
1! = 1
2! = 2 ● 1 = 2
3! = 3 ● 2 ● 1 = 6
4! = 4 ● 3 ● 2 ● 1 = 24
5! = 5 ● 4 ● 3 ● 2 ● 1 = 120
Notice that as n increases, n! becomes very large.
Take some time now to learn how to use the
factorial key on your calculator. On a TI-84, go
to math|prb|4
Example 3: Finding the number of
permutations of n objects
• The starting lineup for a baseball team
consists of nine players. How many
different batting orders are possible using
the starting lineup?
Solution: the number of permutations is 9!
9! = 9 ● 8 ● 7 ● 6 ● 5 ● 4 ● 3 ● 2 ● 1 = 362,880
Permutations of n objects taken r at a time
• Suppose you want to choose some of
the objects in a group and put them in
order. Such an ordering is called a
permutation of n objects taken r at a
time.
P
n
r
n!

(n  r )!
Where r  n
Example 4: Finding n P r
Find the number of ways of forming
three-digit codes in which no digit is
repeated.
nPr=
10 P 3
10!
10!


(10  3)! 7!
10  9  8  7  6  5  4  3  2  1

7  6  5  4  3  2 1
 720
There are 720 possible three-digit codes that do not have
repeating digits.
Example 5: Finding n P r
Forty-three race cars started the 2007 Daytona 500. How many ways
can the cars finish first, second, and third?
Because there are 43 race cars and order is important, the number of
ways the cars can finish first, second, and third is:
n P r = 43 P 3
43!
43!


(43  3)! 40!
 43  42  41
 74,046
Ordering same objects
Suppose you want to order a group of n objects where some of
the objects are the same. For instance, consider a group of
letters consisting of four A’s, 2 B’s, and one C. How many
ways can you order such a group? Using the previous
formula, you might conclude the following:
nPr= 7
P 7 = 7!
However, because some of the objects are the
same, not all of these permutations are
distinguishable. How many distinguishable
permutations are possible. The answer can be
found using the formula on the next slide.
Distinguishable Permutations
n!
, where
n1!n2 !n3!    nk !
n1  n2  n3  ...  nk  n.
7!
7  6  5  4  3  2 1


4!2!1!
4!2!1!
765

2
 105
Example 6: Distinguishable
Permutations
• A building contractor is planning to develop a
subdivision. The subdivision consists of six
one-story houses, four two-story houses, and
two split-level houses. In how many
distinguishable ways can the houses be
arranged?
Solution: There are to be twelve houses in the
subdivision (6+4+2)
Example 6: Distinguishable Permutations
12!
12  11  10  9  8  7  6  5  4  3  2  1


6!4!2!
6!4!2!
12  11  10  9  8  7  6  5  4  3  2  1

(6  5  4  3  2  1)( 4  3  2  1)( 2  1)
12  11  10  9  8  7

(4  3  2  1)( 2  1)
665,280

48
 13,860
Combinations
Suppose you want to buy three CD’s from a selection of
five CD’s. There are 10 ways to make your selections
ABC,ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE.
In each selection, order does NOT matter. (ABC is the
same set as BAC). The number of ways to choose r
objects from n objects without regard to order is called
the number of combinations of n objects taken r at a
time.
Combination of Objects taken r at a time
• A combination is a selection of r objects
from a group of n objects without regard
to order and is denoted by n C r. The
number of combinations of r objects
selected from a group of n objects is:
n!
n Cr 
(n  r )! r!
Example 7: Finding the number of
combinations
A state’s department of
transportation plans to develop
a new section of interstate
highway and receives 16 bids
for the project. The state plans
to hire four of the bidding
companies. How many
different combinations of four
companies can be selected
from the 16 bidding
companies? Because order is
NOT important, there are:
16!
16 C 4 
(16  4)!4!
16!

12!4!
16  15  14  13

4  3  2 1
43680

 1820
24
Applications – Example 8 Finding
Probabilities
A word consists of one M, four I’s, four S’s, and two P’s.
If the letters are randomly arranged in order, what is
the probability that the arrangement spells the word
Mississippi? Solution. There is one favorable outcome
and there are
11!
There are 34,650
distinguishable
1!4!4!2!
permutations of the
11  10  9  8  7  6  5

word Mississippi.
4  3  2 1 2 1
So the probability
1663200
that the

arrangement spells
48
the word
 34650
Mississippi is:
Applications – Example 8 Finding
Probabilities
There are 34,650 distinguishable permutations of the
word Mississippi. So the probability that the
arrangement spells the word Mississippi is:
1
P( Mississipp i) 
 .000029
34,650
Applications – Example 9 Finding
Probabilities
Find the probability of being dealt five diamonds from a
standard deck of playing cards. (In poker, this is a
diamond flush.)
SOLUTION: The possible number of way of choosing 5
diamonds out of 13 is 13C5. The number of possible 5
card hands is 52C5. So the probability of being dealt 5
diamonds is:
C5
1287
P( DiamondFlu sh) 

2,598,960
52 C5
13
 .0005
Resources
C r chart
http://www.rpbridge.net/7z78.htm --has up
to 52 for n. Readable and will save you
some time especially after that last
problem.
Permutations Calculator (Tech tool)
http://www.mathsisfun.com/combinatorics/co
mbinations-permutations-calculator.html
n