Transcript permutation

PERMUTATIONS
AND
COMBINATIONS
BOTH
PERMUTATIONS AND
COMBINATIONS
USE A COUNTING METHOD
CALLED FACTORIAL.
A FACTORIAL is a counting method
that uses consecutive whole numbers as
factors.
The factorial symbol is !
Examples
5! = 5x4x3x2x1
= 120
7! = 7x6x5x4x3x2x1
= 5040
First, we’ll do some
permutation problems.
Permutations are
“arrangements”.
Permutations
In the context of counting problems,
arrangements are often called permutations;
the number of permutations of n things taken r
at a time is denoted nPr. Applying the
fundamental counting principle to
arrangements of this type gives
nPr =
n(n – 1)(n – 2)…[n – (r – 1)].
Factorial Formula for Permutations
The number of permutations, or
arrangements, of n distinct things taken r at a
time, where r  n, can be calculated as
n!
.
n Pr 
(n  r )!
Example: Permutations
Evaluate each permutation.
a) 5P3
b) 6P6
Solution
5!
5!
a) 5 P3 
  60
(5  3)! 2!
6!
6!
b) 6 P6 
  720
(6  6)! 0!
Example: IDs
How many ways can you select two letters followed
by three digits for an ID if repeats are not allowed?
Solution
There are two parts:
1. Determine the set of two letters.
2. Determine the set of three digits.
26 P2  10 P3
Part 1 Part 2
 650  720  468,000
Example: Building Numbers From a Set of Digits
How many four-digit numbers can be written using
the numbers from the set {1, 3, 5, 7, 9} if repetitions
are not allowed?
Solution
Repetitions are not allowed and order is important, so
we use permutations:
5!
5!
  120.
5 P4 
(5  4)! 1!
Let’s do a permutation problem.
How many different arrangements are
there for 3 books on a shelf?
Books A,B, and C can be arranged in
these ways:
ABC ACB BAC BCA CAB CBA
Six arrangements or 3! = 3x2x1 = 6
In a permutation, the order of the
books is important.
Each different permutation is a
different arrangement.
The arrangement ABC is different
from the arrangement CBA, even
though they are the same 3 books.
You try this one:
1. How many ways can 4 books be arranged on a shelf?
4! or 4x3x2x1 or 24 arrangements
Here are the 24 different arrangements:
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA
Now we’re going to do 3 books on a
shelf again, but this time we’re going
to choose them from a group of 8
books.
We’re going to have a lot more
possibilities this time, because there
are many groups of 3 books to be
chosen from the total 8, and there are
several different arrangements for each
group of 3.
If we were looking for different
arrangements for all 8 books,
then we would do 8!
But we only want the
different arrangements for
groups of 3 out of 8, so we’ll
do a partial factorial,
8x7x6
=336
Try these:
1. Five books are chosen from a group
of ten, and put on a bookshelf. How
many possible arrangements are there?
10x9x8x7x6 or
30240
2. Choose 4 books from a group of 7
and arrange them on a shelf. How many
different arrangements are there?
7x6x5x4
or
840
Combinations
Combinations
In the context of counting problems, subsets,
where order of elements makes no difference,
are often called combinations; the number of
combinations of n things taken r at a time is
denoted nCr.
Factorial Formula for Combinations
The number of combinations, or subsets, of n
distinct things taken r at a time, where r  n,
can be calculated as
n Pr
n!

.
n Cr 
r ! r !(n  r )!
n!
n!

n Cnr .
Note: n Cr 
r !(n  r )! (n  r )!r !
Example: Combinations
Evaluate each combination.
a) 5C3
b) 6C6
Solution
5!
5!
a) 5C3 

 10
3!(5  3)! 3!2!
6!
6!
b) 6C6 

1
6!(6  6)! 6!0!
Now, we’ll do some
combination problems.
Combinations are
“selections”.
There are some problems where the
order of the items is NOT important.
These are called combinations.
You are just making selections, not
making different arrangements.
Example: A committee of 3 students must be
selected from a group of 5 people. How
many possible different committees could be
formed?
Let’s call the 5 people A,B,C,D,and E.
Suppose the selected committee consists
of students E, C, and A. If you rearrange the names to C, A, and E, it’s
still the same group of people. This is
why the order is not important.
Because we’re not going to use all the
possible combinations of ECA, like EAC,
CAE, CEA, ACE, and AEC, there will be a
lot fewer committees.
Therefore instead of using only 5x4x3, to get
the fewer committees, we must divide.
5x4x3
Answer:
3x2x1
10
committees
(Always divide by
the factorial of the
number of digits
on top of the
fraction.)
Now, you try.
1. How many possible committees of 2
people can be selected from a group of 8?
8x7
2x1
or 28 possible
committees
2. How many committees of 4 students
could be formed from a group of 12
people?
12x11x10x9
4x3x2x1
or 495 possible
committees
Example: Finding the Number of Subsets
Find the number of different subsets of size 3
in the set {m, a, t, h, r, o, c, k, s}.
Solution
A subset of size 3 must have 3 distinct elements,
so repetitions are not allowed. Order is not
important.
9!
9!

 84
9 C3 
3!(9  3)! 3!6!
Example: Finding the Number of Poker Hands
A common form of poker involves hands (sets) of five
cards each, dealt from a deck consisting of 52 different
cards. How many different 5-card hands are possible?
Solution
Repetitions are not allowed and order is not
important.
52!
52!

 2,598,960
52 C5 
5!(52  5)! 5!47!
Guidelines on Which Method to Use
Permutations
Combinations
Number of ways of selecting r items out of n items
Repetitions are not allowed
Order is important.
Order is not important.
Arrangements of n items
taken r at a time
nPr = n!/(n – r)!
Subsets of n items taken r
at a time
nCr = n!/[ r!(n – r)!]
Clue words: arrangement, Clue words: group,
schedule, order
sample, selection
Permutations and Combinations
Evaluate each problem.
b) 5C3
a) 5P3
c) 6P6
d) 6C6
543
60
10
720
1
Permutations and Combinations
How many ways can you select two letters followed by three
digits for an ID if repeats are not allowed?
Two parts:
1. Determine the set of two letters. 2. Determine the set of three digits.
26P2
10P3
2625
650
650720
468,000
1098
720
Permutations and Combinations
A common form of poker involves hands (sets) of five cards each, dealt
from a deck consisting of 52 different cards. How many different 5-card
hands are possible?
Hint: Repetitions are not allowed and order is not important.
52C5
2,598,960
5-card hands
Permutations and Combinations
Find the number of different
subsets of size 3 in the set:
{m, a, t, h, r, o, c, k, s}.
9C3
Find the number of arrangements
of size 3 in the set:
{m, a, t, h, r, o, c, k, s}.
9P3
987
504
84
Different
subsets
arrangements
10.3 – Using Permutations and Combinations
Guidelines on Which Method to Use
CIRCULAR
PERMUTATIONS
When items are in a circular
format, to find the number of
different arrangements,
divide:
n! / n
Six students are sitting
around a circular table in
the cafeteria. How many
different seating
arrangements are there?
6!  6 = 120
Fundamental Counting
Principle
For a college interview, Robert has to choose
what to wear from the following: 4 slacks, 3
shirts, 2 shoes and 5 ties. How many possible
outfits does he have to choose from?
4*3*2*5 = 120 outfits
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?
Permutations
Practice:
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!
From a club of 24 members, a
President, Vice President, Secretary,
Treasurer and Historian are to be
elected. In how many ways can the
offices be filled?
Permutations
Answer:
From a club of 24 members, a
President, Vice President, Secretary,
Treasurer and Historian are to be
elected. In how many ways can the
offices be filled?
24!
24!


24 p5 
( 24  5)! 19!
24 * 23 * 22 * 21 * 20  5,100,480
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?
Combinations
Answer:
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
A student must answer 3 out of 5
essay questions on a test. In how
many different ways can the
student select the questions?
Combinations
Answer:
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
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?
Combinations
Answer:
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?
Center:
Forwards:
Guards:
2!
5! 5 * 4
4! 4 * 3
C



10
C


2

6
5 2
2
1
4 C2 
2!3! 2 * 1
2!2! 2 * 1
1!1!
2
C1 * 5 C 2 * 4 C 2
Thus, the number of ways to select the
starting line up is 2*10*6 = 120.
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.
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.
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.
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.
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 many ways
can the prizes be awarded? 720
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
Tournament
Problems
An amusement park has 27 different
rides. If you have 21 ride tickets, how
many different combinations of
rides can you take?
Answer:
296,010
Pop’s Pizza offers 4 types of meat and
3 types of cheese. In how many ways
could a pizza with two meats, different
or double of the same meat, and one
cheese be ordered?
Answer:
30
Pop’s Pizza offers 4 types of meat and
3 types of cheese. In how many ways
could a pizza with two meats, different
or double of the same meat, and one
cheese be ordered?
Answer:
30