Transcript counting-principle-and-permutations

THE FUNDAMENTAL
COUNTING PRINCIPLE
& PERMUTATIONS
Computer Science, Statistics and Probability all involve counting techniques
which are a branch of mathematics called combinatorics (ways to combine
things). We'll be introducing this topic in this section.
For dinner you have the following choices:
ENTREES
soup
MAINS
salad
chicken
prawns
hamburger
DESSERTS
How many different combinations of meals
could you make?
icecream

We'll build a tree diagram to show all of
the choices.
Notice the number of choices at each branch
2
choices
3
choices
2
choices
We ended up with
12 possibilities
soup, chicken, ice cream
soup, chicken, 
2  3  2 = 12
prawns
soup, prawns, ice cream
soup, prawns, 
soup, hamburger, ice cream
soup, hamburger, 
salad, chicken, ice cream
salad, chicken, 
prawns
salad, prawns, ice cream
salad, prawns, 
Now to get all possible
choices we follow each
path.
salad, hamburger, ice cream
salad, hamburger, 
THE FUNDAMENTAL COUNTING
PRINCIPLE & PERMUTATIONS
ESSENTIAL QUESTION
How is the counting principle
applied to determine outcomes?
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
different ways.
pqr
If we have 6 different shirts, 4 different pants, 5 different pairs of socks and 3
different pairs of shoes, how many different outfits could we wear?
6  4  5  3 = 360
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.
How many different dinners (one choice of
each) can you choose?
8*2*12*6=
1152 different dinners
FUNDAMENTAL COUNTING
PRINCIPLE WITH REPETITION
Ohio Licenses plates have 3 #’s followed
by 3 letters.
1. 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?
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
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 Fundamental
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