Transcript permutation

Warm Up
Evaluate.
1. 5  4  3  2  1
120
2. 7  6  5  4  3  2  1 5040
3.
4
4.
5.
10
6.
210
70
You have previously used
tree diagrams to find
the number of possible
combinations of a group of
objects. In this lesson, you
will learn to use the
Fundamental Counting
Principle.
Example 1A: Using the Fundamental Counting
Principle
To make a yogurt parfait, you choose one
flavor of yogurt, one fruit topping, and one nut
topping. How many parfait choices are there?
Yogurt Parfait
(choose 1 of each)
Flavor
Plain
Vanilla
Fruit
Peaches
Strawberries
Bananas
Raspberries
Blueberries
Nuts
Almonds
Peanuts
Walnuts
Example 1A Continued
number
number
number
number
equals
of
times of fruits times of nuts
of choices
flavors
2

5

There are 30 parfait choices.
3
=
30
Example 1B: Using the Fundamental Counting
Principle
A password for a site consists of 4 digits
followed by 2 letters. The letters A and Z are
not used, and each digit or letter many be used
more than once. How many unique passwords
are possible?
digit digit digit digit letter letter
10  10  10  10  24  24 = 5,760,000
There are 5,760,000 possible passwords.
Check It Out! Example 1a
A “make-your-own-adventure” story lets you
choose 6 starting points, gives 4 plot choices,
and then has 5 possible endings. How many
adventures are there?
number
of
starting
points
6


number
of plot
choices
4

number
of
possible
endings
=

5
=
There are 120 adventures.
number
of
adventures
120
Check It Out! Example 1b
A password is 4 letters followed by 1 digit.
Uppercase letters (A) and lowercase letters (a)
may be used and are considered different. How
many passwords are possible?
Since both upper and lower case letters can be used,
there are 52 possible letter choices.
letter letter letter letter number
52
 52  52 
52 
10
= 73,116,160
There are 73,116,160 possible passwords.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
A permutation is a selection of a group of objects in
which order is important.
There is one way to
arrange one item A.
A second item B can
be placed first or
second.
A third item C
can be first,
second, or third
for each order
above.
1 permutation
2·1
permutations
3·2·1
permutations
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
You can see that the number of permutations of 3 items
is 3 · 2 · 1. You can extend this to permutations of n
items, which is n · (n – 1) · (n – 2) · (n – 3) · ... · 1.
This expression is called n factorial, and is written as n!.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Sometimes you may not want to order an entire set of
items. Suppose that you want to select and order 3
people from a group of 7. One way to find possible
permutations is to use the Fundamental Counting
Principle.
First
Person
7

choices
Second
Person
6
choices
Third
Person
5

choices
There are 7 people.
You are choosing 3
of them in order.
=
210
permutations
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Another way to find the possible permutations is to use
factorials. You can divide the total number of
arrangements by the number of arrangements that are
not used. In the previous slide, there are 7 total people
and 4 whose arrangements do not matter.
arrangements of 7 = 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 210
arrangements of 4
4!
4·3·2·1
This can be generalized as a formula, which is useful
for large numbers of items.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Example 2A: Finding Permutations
How many ways can a student government
select a president, vice president, secretary, and
treasurer from a group of 6 people?
This is the equivalent of selecting and arranging 4
items from 6.
Substitute 6 for n and 4 for r in
Divide out common factors.
= 6 • 5 • 4 • 3 = 360
There are 360 ways to select the 4 people.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Example 2B: Finding Permutations
How many ways can a stylist arrange 5 of 8
vases from left to right in a store display?
Divide out common
factors.
=8•7•6•5•4
= 6720
There are 6720 ways that the vases can be arranged.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Check It Out! Example 2a
Awards are given out at a costume party. How
many ways can “most creative,” “silliest,” and
“best” costume be awarded to 8 contestants if
no one gets more than one award?
=8•7•6
= 336
There are 336 ways to arrange the awards.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Check It Out! Example 2b
How many ways can a 2-digit number be formed
by using only the digits 5–9 and by each digit
being used only once?
=5•4
= 20
There are 20 ways for the numbers to be formed.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
A combination is a grouping of items in which order
does not matter. There are generally fewer ways to
select items when order does not matter. For
example, there are 6 ways to order 3 items, but they
are all the same combination:
6 permutations  {ABC, ACB, BAC, BCA, CAB, CBA}
1 combination  {ABC}
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
To find the number of combinations, the formula for
permutations can be modified.
Because order does not matter, divide the number of
permutations by the number of ways to arrange the
selected items.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Permutations
Warm Up:
A combination lock will open when the
right choice of three numbers (from 1
to 30, inclusive) is selected. How many
different lock combinations are possible
assuming no number is repeated?
30!
30!

 30 * 29 * 28  24360
30 p3 
( 30  3)! 27!
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Three Types of
Permutations
1. Distinct with repetition.
Let's look at a 3 combination
lock with numbers 0 through 9
There are 10 choices for the first number
There are 10 choices for the second number
and you can repeat the first number
There are 10 choices for the third number
and you can repeat
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Three Types of
Permutations
2. Distinct without repetition.
Let's say four people have a race. Let's look at
the possibilities of how they could place. Once a
person has been listed in a place, you can't use
that person again (no repetition).
4th
3rd
2nd
1st
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
When deciding whether to use permutations or
combinations, first decide whether order is important.
Use a permutation if order matters and a combination
if order does not matter.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Helpful Hint
You can find permutations and combinations by
using nPr and nCr, respectively, on scientific and
graphing calculators.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Example 3: Application
There are 12 different-colored cubes in a bag.
How many ways can Randall draw a set of 4
cubes from the bag?
Step 1 Determine whether the problem represents
a permutation of combination.
The order does not matter. The cubes may be
drawn in any order. It is a combination.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Example 3 Continued
Step 2 Use the formula for combinations.
n = 12 and r = 4
5
Divide out
common
factors.
= 495
There are 495 ways to draw 4 cubes from 12.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Check It Out! Example 3
The swim team has 8 swimmers. Two swimmers
will be selected to swim in the first heat. How
many ways can the swimmers be selected?
n = 8 and r = 2
Divide out
common
factors.
4
= 28
The swimmers can be selected in 28 ways.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Combinations
To play a particular card game, each
player is dealt five cards from a
standard deck of 52 cards. How
many different hands are possible?
52!
52!


52 C5 
5! (52  5)! 5!47!
52 * 51 * 50 * 49 * 48
 2,598,960
5* 4* 3* 2*1
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Combinations
A student must answer 3 out of 5
essay questions on a test. In how
many different ways can the
student select the questions?
5!
5! 5 * 4


 10
5 C3 
3! (5  3)! 3!2! 2 * 1
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Three Types of
Permutations
3. Involving n objects that are not distinct.
Let's say four people have a race. Let's look at the possibilities
of how they could place. Once a person has been listed in a
place, you can't use that person again (no repetition).
E
R
N
R
A
A
G
E
R
The third type of permutation is involving n objects that
are not distinct.
How many different combinations of letters in specific
order (but not necessarily English words) can be formed
using ALL the letters in the word REARRANGE?
Not Examinable.. Just for Fun 
E
R
N
R
A
A
G
E
R
The "words" we form will have 9 letters so we need 9 spots to
place the letters. Notice some of the letters repeat. We need
to use R 3 times, A 2 times, E 2 times and N and G once.
6C
4C
9C


 2C1  1C1
2
2
3
84  15  6  2  1 = 15 120
possible "words"
That leaves
First we choose
positions for the
R's. There are 9 That leaves
positions and we'll 6 positions
choose 3, order for 2 A's.
doesn't matter
That leaves
4 positions
for 2 E's.
2 positions
for the N.
That leaves
1 position
for the G.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Combinations
A basketball team consists of two centers, five forwards,
and four guards. In how many ways can the coach select a
starting line up of one center, two forwards, and two
guards?
Forwards:
2!
5! 5 * 4
C


 10
C


2
5 2
2
1
2!3! 2 * 1
1!1!
Center:
2
Guards:
4! 4 * 3

6
4 C2 
2!2! 2 * 1
C1 * 5 C 2 * 4 C 2
Thus, the number of ways to select the
starting line up is 2*10*6 = 120.
EQ: How do we solve problems involving the Fundamental Counting Principle, and
permutations and combinations?
Lesson Quiz
1. Six different books will be displayed in the
library window. How many different
arrangements are there? 720
2. The code for a lock consists of 5 digits. The
last number cannot be 0 or 1. How many
different codes are possible? 80,000
3. The three best essays in a contest will receive gold,
silver, and bronze stars. There are 10 essays. In how
720
many ways can the prizes be awarded?
4. In a talent show, the top 3 performers of 15 will
advance to the next round. In how many ways can
this be done? 455