Transcript Permutations

Permutations
Counting Techniques, Part 1
Permutations
Recall the notion of calculating the
number of ways in which to arrange a
given number of items.
One tool for accomplishing this task
is the Multiplication Principle.
Permutations
One way to state the multiplication
principle is that to determine the
possible number of outcomes in a given
situation, multiply together the number
of options available every time you
make a choice.
For example, say you want to order a
sundae with 10 flavors of ice cream
and 3 different toppings available.
Permutations
For example, say you want to order a
sundae with 10 flavors of ice cream
and 3 different toppings available.
The total possible number of sundaes
using one scoop of ice cream and one
topping is 10*3, or 30.
Permutations
Another way to state the multiplication
principle is this:
If event A can take place in m ways, and
event B can take place in n ways, then
event A and event B can take place in
m*n ways.
Example: Consider a game where the
player flips a coin and rolls a die.
Permutations
Example: Consider a game where the
player flips a coin and rolls a die.
How many outcomes are possible for
flipping a coin and rolling a die?
There are 2 possible outcomes for the
coin (Heads or Tails) and 6 possible
outcomes for the die (1-6), so there are
2*6, or 12 possible outcomes for the
two events considered together.
Permutations
In some instances, determining the
possible number of outcomes
requires the use of the
Addition Principle.
Here’s one statement of the addition
principle:
If event A can occur in m ways and
event B can occur in n ways, then event
A or event B can occur in m + n ways.
Permutations
Comparing the multiplication and
addition principles:
A school club consists of 14 Juniors and
18 Seniors. In how many ways could we
select a committee of 2 students if one
must be a Junior and one must be a
Senior?
We have 14 options for the Junior, and
18 options for the Senior, so we have a
total of 14*18, or 252 possibilities.
Permutations
Comparing the multiplication and
addition principles:
A school club consists of 14 Juniors and
18 Seniors. How many options do we
have for a representative if either a
Junior or Senior can fill the position?
We have 14 options for a Junior, and 18
options for a Senior, so we have a total
of 14 + 18, or 32 possibilities.
Permutations
Comparing the multiplication and
addition principles:
Recall that in some cases we needed
to modify the multiplication
principle—namely when order does
not matter. For example, when
picking two numbers from a list of
10, we have (10*9)/2, or 45
possibilities.
Permutations
Comparing the multiplication and
addition principles:
We needed to divide by 2 to take into
account the fact that we had counted
every pair of numbers twice.
I.e., we counted (1, 2) as well as (2, 1)
even though they are the same pair
of numbers, and should only count
once.
Permutations
Comparing the multiplication and
addition principles:
Likewise, we sometimes need to
modify the addition principle.
Permutations
Consider a committee that requires either a
soccer player or a track athlete. For this
example, say the athletes are in a school
where they cannot compete in both soccer
and track, due to the two sports being in the
same season.
If there are 40 soccer players and 60
track athletes, how many possibilities
are there to select a representative?
Permutations
Because an athlete cannot compete
in both sports in this case:
Soccer
Track
40
60
We have 40 + 60, or 100 possibilities.
Permutations
Now consider a committee that
requires either a soccer player or a
band member.
If there are 40 soccer players and 80
band members, how many
possibilities are there to select a
representative?
Permutations
In this case, a student could be a
member of both groups:
Soccer
Band
40
80
Because of the overlap between the two
groups, we cannot simply add 40 + 80 and
be done with it. We will need to subtract
out the number of students that are in both.
Permutations
In this case, a student could be a
member of both groups:
Band
Soccer
10
40
80
If there are 10 students involved in both
groups, then we have 40 + 80 – 10, or
110 possibilities for a representative.
Permutations
In the case of soccer and track, the
two groups are mutually exclusive, or
disjoint, because it is not possible to
be part of both groups.
Soccer
Track
40
60
Permutations
In the case of soccer and band, the
two groups are not mutually
exclusive.
Band
Soccer
40
10
80
We must make our adjustment to the
addition principle when events are not
mutually exclusive.
Permutations
In some instances we can use the
multiplication principle and the
addition principle together.
Say there is a lottery where a player can
arrange (order matters) either 2, 3, or 4
numbers from the numbers 1-20.
(Naturally the player who matches 4
numbers wins more money than the
player who only matches 2 numbers.)
Permutations
In how many ways can a
player fill out a card?
First, consider the number of ways to arrange 2
numbers from the numbers 1-20:
We have 20 choices for the first number, and
then 19 for the second number, so we have
20*19, or 380 possibilities.
Permutations
In how many ways can a
player fill out a card?
The number of ways to arrange 3
numbers:
We have 20 choices for the first number,
19 for the second number, and then 18
for the third number, so we have
20*19*18, or 6,840 possibilities.
Permutations
In how many ways can a
player fill out a card?
The number of ways to arrange 4
numbers:
20*19*18*17 = 116,280 possibilities.
Permutations
In how many ways can a
player fill out a card?
Finally, to determine the number of ways
to fill out a card, we need to add together
the possibilities for 2 numbers, for 3
numbers, and for 4 numbers:
380 + 6,840 + 116,280 = 123,500 ways.
Can you see why the person matching 4
numbers would win so much more money
than someone matching 2 numbers?
Permutations
We have now seen several examples
of what are called permutations.
Permutations are the arrangements of a
group of items where order matters.
We often calculate permutations in a
scenario by using the multiplication
principle.
Permutations
Example: In how many ways can
choose to watch 3 movies?
You have 3 options for your first movie.
After choosing the first movie, you will
have 2 options remaining for the second
movie. After choosing the first and second
movies, only 1 option remains for the third
movie.
This gives you 3*2*1, or 6 ways to arrange
3 movies.
Permutations
Example: In how many ways can a
baseball manager arrange a hitting
order for 9 batters?
The manager has 9 options for the
leadoff hitter, then 8 options for the
second hitter, then 7 options for the
third hitter, and so forth. In total, the
manager has
9*8*7*6*5*4*3*2*1,
or 362,880 possible lineups.
Permutations
Notice that the answers can get quite
large, very quickly.
Example: How many seating charts
could a teacher make for 20 students, if
there are 20 desks in the room?
The teacher has 20 options for the first
desk, then 19 options for the second desk,
then 18 options for the third desk, and so
forth. In total, the teacher has
20*19*18*17*…*5*4*3*2*1,
or 2,432,902,008,176,640,000 possibilities.
Permutations
Notice that the answers can get quite
large, very quickly.
Example: How many seating charts
could a teacher make for 20 students, if
there are 20 desks in the room?
We usually represent a number this
large by using scientific notation:
2,432,902,008,176,640,000
might be rounded to 2.43*1018.
Permutations
When dealing with extended
multiplications as in the previous
examples, wouldn’t it be nice to have
a shortcut?
Permutations
When dealing with extended
multiplications as in the previous
examples, wouldn’t it be nice to have
a shortcut?
Great news—we do!
Permutations
Do you remember using factorials
back in your days of studying
Algebra? We can use them again in
these problems.
Example: The number of ways to
arrange 3 movies:
3*2*1 = 3! (read 3 factorial)
Permutations
Example: Arranging a batting order
for 9 players:
9*8*7*6*5*4*3*2*1 = 9!
Example: Seating charts for 20 students
with 20 desks:
20*19*18*17*…*5*4*3*2*1 = 20!
Permutations
One reason this notation is so useful is
because most calculators (as well as
computer spreadsheets) have a factorial
function included, making the
calculations quite simple.
Permutations
On a typical graphing calculator, look
for a button labeled “MATH.”
After pressing that button, look for a
heading labeled “PROBABILITY” or
something like “PRB” for short. You
might need to use the right arrow to
get to that section.
Once in the probability section, look
for the factorial function (!).
Permutations
To determine the value of 9! using
the calculator follow these steps:
•Enter 9
•Press MATH
•Move to the probability section
•Move the cursor to !
•Press ENTER—you should see 9!
•Press ENTER again to get the answer.
Permutations
The previous examples of
permutations (movies, batting orders,
and seating charts) share a common
feature that makes them relatively
simple: they arranged all of the
available items.
This won’t always be the case.
Permutations
Example: You want to pick 4 movies
out of 10, and then select an order for
viewing them.
In this case, we cannot simply say the
answer is 4!, because we are choosing
from more than 4 movies.
Permutations
Example: You want to pick 4 movies
out of 10, and then select an order for
viewing them.
We have 10 options for the first movie.
After picking that, we have 9 options for
the second movie, 8 options for the
third movie, and finally 7 options for the
fourth movie.
Permutations
Example: You want to pick 4 movies
out of 10, and then select an order for
viewing them.
This gives us
10*9*8*7, or 5,040 total possibilities.
Permutations
Example: You want to pick 4 movies
out of 10, and then select an order for
viewing them.
When only ordering 4 items, this is no
headache. With a larger number of
items, though, it would be nice to have
a more compact formula.
Permutations
Example: You want to pick 4 movies
out of 10, and then select an order for
viewing them.
Notice that we can rewrite 10*9*8*7 as
10*9*8*7*6*5*4*3*2*1
6*5*4*3*2*1
(We multiply by 6*5*4*3*2*1, and then divide by the
same amount.)
Permutations
Example: You want to pick 4 movies
out of 10, and then select an order for
viewing them.
This sneaky little trick allows us to
rewrite 10*9*8*7 as
10!
6!
Permutations
Example: You want to pick 4 movies
out of 10, and then select an order for
viewing them.
Notice the numerator is the factorial of the
number of items available, while the
denominator is the factorial of the difference
between the number of items available and the
number of items we’re arranging.
10!
= __10!__
6!
(10-4)!
Permutations
In general, if we have n items and
want to arrange m of them, we will
have
__n!__
(n-m)!
permutations.
Permutations
Several other notations are commonly
used to express this value:
P(n, m)
n Pm
Permutations
Graphing calculators often use a function
labeled
nPr
The user enters the total number of
items, finds the nPr function, and then
enters the number of items to be
arranged.
(Example to follow.)
Permutations
Example: A baseball manager wants to
arrange a batting lineup for 9 players,
and has 15 players from which to
choose. How many batting orders can
the manager create?
One solution would be to multiply the
individual options:
15*14*13*12*11*10*9*8*7
Permutations
Example: A baseball manager wants to
arrange a batting lineup for 9 players,
and has 15 players from which to
choose. How many batting orders can
the manager create?
Another solution, and one which will prove
useful in problems with larger numbers,
would be to use our formula for
permutations:
Permutations
Example: A baseball manager wants to
arrange a batting lineup for 9 players,
and has 15 players from which to
choose. How many batting orders can
the manager create?
P(15, 9) =
__15!__
=
(15-9)!
15!
6!
Permutations
Using the permutation function on a
graphing calculator:
•Enter 15 (the total number of players)
•Press MATH
•Move the cursor to the PRB section
•Move the cursor down to nPr
•Press ENTER
•Enter 9 (the number of players to arrange)
•Press ENTER to get the answer
Permutations
Do you remember how the number of
seating charts for 20 students was so large?
Now consider a case where there are still
20 students, but there are 25 desks in the
room. How many seating charts are now
possible?
Go ahead and guess! 
Permutations
Do you remember how the number of
seating charts for 20 students was so large?
Now consider a case where there are still
20 students, but there are 25 desks in the
room. How many seating charts are now
possible?
P(25, 20) = 1.29*1023 or
129,000,000,000,000,000,000,000