Transcript 12.1 The Fundamental Counting Principal

10.1
- The Fundamental Counting Principal
- Permutations
- Factorials
The Fundamental Counting Principle
• If you have 2 events: 1 event can occur m ways and
another event can occur n ways, then the number of
ways that both can occur is m*n
• Event 1 = 4 types of meats
• Event 2 = 3 types of bread
How many diff types of sandwiches can you make?
4*3 = 12
3 or more events:
• 3 events can occur m, n, & p ways, then the
number of ways all three can occur is m*n*p
• 4 meats
• 3 cheeses
• 3 breads
How many different sandwiches can you make?
4*3*3 = 36 sandwiches
At a restaurant at Cedar Point, you have the choice of
8 different entrees, 2 different salads, 12 different
drinks, & 6 different deserts.
Question: How many different dinners can you choose
(one choice of each)?
8*2*12*6=
1152 different dinners
Fundamental Counting Principle
with Repetition
Let’s say, Ohio Licenses plates have 3 #’s followed
by 3 letters.
How many different licenses plates are possible if
digits and letters can be repeated?
There are 10 choices for digits and 26 choices for
letters.
10*10*10*26*26*26=
17,576,000 different plates
How many plates are possible if digits and
numbers cannot be repeated?
Same situation with license plates…but a number or
letter cannot be repeated.
There are still 10 choices for the 1st digit, but only 9
choices for the 2nd, and 8 for the 3rd.
For the letters, there are 26 for the first, but only 25 for
the 2nd and 24 for the 3rd.
10*9*8*26*25*24 =
11,232,000 plates
Phone numbers
• How many different 7 digit phone numbers are
possible if the 1st digit cannot be a 0 or 1?
• 8*10*10*10*10*10*10=
• 8,000,000 different numbers
PASSWORDS
Let’s pick a password….
a) 4 using digits only
PASSWORDS
Let’s pick a password….
b) 4 using digits or letters (not case sensitive)
PASSWORDS
Let’s pick a password….
c) 4 using digits or letters (upper/lower case sensitive)
Testing
A multiple choice test has 10 questions with 4
answers each. How many ways can you
complete the test?
• 4*4*4*4*4*4*4*4*4*4 = 410 =
• 1,048,576
Using Permutations
• An ordering of n objects is a
permutation of the objects.
There are 6 permutations of the letters A, B, &C
•
•
•
•
•
•
ABC
ACB
BAC
BCA
CAB
CBA
You can use the
Fund. Counting Principle to
determine the number of
permutations of n objects.
Like this ABC.
There are 3 choices for 1st #
2 choices for 2nd #
1 choice for 3rd.
3*2*1 = 6 ways to arrange the
letters
In general,
the # of permutations of n objects is:
n! = n*(n-1)*(n-2)* …
12 skiers…
• How many different ways can 12 skiers in the
Olympic finals finish the competition? (if there
are no ties)
12! = 12*11*10*9*8*7*6*5*4*3*2*1
479,001,600 different ways
Factorial with a
calculator:
•Hit math then over, over,
over.
•Option 4
Back to the finals in the Olympic
skiing competition.
• How many different ways can 3 of the
skiers finish 1st, 2nd, & 3rd (gold, silver,
bronze)
• Any of the 12 skiers can finish 1st, the any
of the remaining 11 can finish 2nd, and any
of the remaining 10 can finish 3rd.
• So the number of ways the skiers can win
the medals is
• 12*11*10 = 1320
Permutation of n objects taken r at
a time
n
!
•nPr =
n  r !
Back to the last problem with the
skiers
• It can be set up as the number of
permutations of 12 objects taken 3 at a
time.
• 12P3 = 12! = 12! =
(12-3)!
9!
• 12*11*10*9*8*7*6*5*4*3*2*1 =
•
9*8*7*6*5*4*3*2*1
12*11*10 = 1320
10 colleges, you want to visit all or
some.
• How many ways can you visit
6 of them:
• Permutation of 10 objects taken 6 at a
time:
• 10P6 = 10!/(10-6)! = 10!/4! =
• 3,628,800/24 = 151,200
How many ways can you visit
all 10 of them:
• 10P10 =
• 10!/(10-10)! =
• 10!/0!=
• 10! = ( 0! By definition = 1)
• 3,628,800
How many different ways can we
arrange the letters A, B, &C
•
•
•
•
•
•
ABC
ACB
BAC
BCA
CAB
CBA
3!
If some of the objects are repeated, then some
of the permutations are not distinguishable.

There are 6 ways to order the letters M,O,M
MOM, OMM, MMO
MOM, OMM, MMO

Only 3 are Distinguishable.


3!
3
2!
Find the number of Distinguishable
permutations of the letters:
• OHIO : 4 letters with O repeated 2 times
• 4! = 24 = 12
• 2! 2
• MISSISSIPPI : 11 letters with I repeated 4
times, S repeated 4 times, P repeated 2 times
•
11! = 39,916,800 = 34,650
• 4!*4!*2! 24*24*2

SUMMER

360

WATERFALL

90,720
Permutations with Repetition
• The number of DISTINGUISHABLE
permutations of n objects where one
object is repeated q1 times, another is
repeated q2 times, and so on :
•
n!
q1! * q2! * … * qk!
A dog has 8 puppies, 3 male and 5
female. How many birth orders are
possible by gender.
• 8!/(3!*5!) =
• 56
Assignment