### permutation___combination

Permutations
and
Combinations
Here are the 3 cleans shirts that Ed had in
the last presentation.
Here are the 3 cleans shirts that Ed had in
the last presentation.
If he’s going to wear a different one each
day on Monday, Tuesday, and Wednesday,
how many choices does he have for
matching up the 3 shirts with the 3 days?
Monday
Tuesday
Wednesday
Ed has 6 choices because he is arranging 3
shirts in order. The number of ways of
doing this is 3 ! 2 ! 1.
Ed has 6 choices because he is arranging 3
shirts in order. The number of ways of doing
this is 3 ! 2 ! 1.
Factorial
n! = n(n-1)(n-2) . . . 1
For example, 5! = 5 ! 4 ! 3 ! 2 ! 1 = 120
Permutations
A permutation of a set of objects is a listing of
the objects in some specified order. The
number of different permutations of n different
objects is given by n!.
A baseball team has nine players. How many
different possible batting orders are there once
it has been decided who the starting players will
be? How many batting orders are possible if the
pitcher is going to bat last?
A baseball team has nine players. How many
different possible batting orders are there once it
has been decided who the starting players will be?
How many batting orders are possible if the
pitcher is going to bat last?
There are 9 players. The number of ways to write
down a batting order is 9! = 362,880
A baseball team has nine players. How many
different possible batting orders are there once it
has been decided who the starting players will be?
How many batting orders are possible if the
pitcher is going to bat last?
There are 9 players. The number of ways to write
down a batting order is 9! = 362,880
If the pitcher bats last, then the other 8 players
can bat in any order. There are 8! = 40,320
possible arrangements.
P(n,r)
Given a collection of n objects, the number
of different ways in which r of them can be
lined up in a row is
P(n,r) = n(n – 1)(n – 2) ... (n – r + 1).
Such an ordered arrangement of r objects
chosen from n objects is called a
permutation of r objects chosen from n
objects.
Example: P(8,3) = 8 ! 7 ! 6 = 336
If you have five clean shirts and are going
to pick one to wear on Saturday and
another (different) one to wear on
Sunday, how many possible ways can you
If you have five clean shirts and are going
to pick one to wear on Saturday and
another (different) one to wear on
Sunday, how many possible ways can you
Solution:
P(5,2) = 5 ! 4 = 20
If you have five clean shirts and are going
to pack two of them to go on a weekend
trip, how many possibilities are there for
the two that you select?
There are 10 possibilities for which 2 shirts
you pick. The 10 ways are shown here.
Combinations
A set of r objects chosen from a set of n objects is
called a combination of r objects chosen from n
objects. The number of different combinations of r
objects that may be chosen from n given objects is
n!
C(n, r) =
r!(n ! r)!
So C(n,r) represents the number of different
unordered sets of r objects that could be chosen
from a set of n objects.
In the case of the 5 shirts where you were
choosing 2 for the weekend trip, we counted
10 ways to choose 2 shirts from the 5.
This is because
5!
C(5, 2) =
= 10
2!3!
Jerry has seven compact discs that Michelle would
like to borrow for a party. He has agreed to let her
take four of them. In how many different ways
could Michelle make her choice?
Jerry has seven compact discs that Michelle would
like to borrow for a party. He has agreed to let her
take four of them. In how many different ways
could Michelle make her choice?
Michelle will choose 4 of the 7, so she can make
7!
her choice in C(7,4) =
= 35 ways.
4! 3!
Jerry has seven compact discs that Michelle would
like to borrow for a party. He has agreed to let her
take four of them. In how many different ways
could Michelle make her choice?
Michelle will choose 4 of the 7, so she can make
7!
her choice in C(7,4) =
= 35 ways.
4! 3!
The easy way to calculate this: 7 ! 6 ! 5
3!2
A class consists of 14 boys and 17 girls. Four
students from the class are to be selected to go on
a trip.
(a) How many different possibilities are there for
the 4 students selected to make the trip?
(b) If it has been decided that 2 boys and 2 girls will
make the trip, then in how many different ways
could the 4 students be selected?
A class consists of 14 boys and 17 girls. Four
students from the class are to be selected to go on
a trip.
(a) How many different possibilities are there for
the 4 students selected to make the trip?
(b) If it has been decided that 2 boys and 2 girls will
make the trip, then in how many different ways
could the 4 students be selected?
Solution:
(a) C(31,4) =
31!
= 31,465
4! 27!
A class consists of 14 boys and 17 girls. Four
students from the class are to be selected to go on
a trip.
(a) How many different possibilities are there for
the 4 students selected to make the trip?
(b) If it has been decided that 2 boys and 2 girls
will make the trip, then in how many different
ways could the 4 students be selected?
Solution:
31! = 31,465
4! 27!
(b) C(14,2) ! C(17,2) = 91 ! 136 = 12,376
(a) C(31,4) =
A poker hand consists of 5 cards dealt from an
ordinary 52-card deck. How many different poker
hands are there? How many are there that give a
“full house”? (A full house is a hand that contains 3
cards of one rank and 2 cards of some other rank,
for example 3 aces and 2 sevens.)
A poker hand consists of 5 cards dealt from an
ordinary 52-card deck. How many different poker
hands are there? How many are there that give a
“full house”? (A full house is a hand that contains 3
cards of one rank and 2 cards of some other rank,
for example 3 aces and 2 sevens.)
Number of poker hands = C(52,5) = 2,598,960
A poker hand consists of 5 cards dealt from an
ordinary 52-card deck. How many different poker
hands are there? How many are there that give a
“full house”? (A full house is a hand that contains 3
cards of one rank and 2 cards of some other rank,
for example 3 aces and 2 sevens.)
Number of poker hands = C(52,5) = 2,598,960
13 choices for rank of card from which 3 will be
chosen, then 12 choices for rank of card from which
2 will be chosen.
A poker hand consists of 5 cards dealt from an
ordinary 52-card deck. How many different poker
hands are there? How many are there that give a
“full house”? (A full house is a hand that contains 3
cards of one rank and 2 cards of some other rank,
for example 3 aces and 2 sevens.)
Number of poker hands = C(52,5) = 2,598,960
13 choices for rank of card from which 3 will be
chosen, then 12 choices for rank of card from which
2 will be chosen. Then choose 3 cards from the 1st
rank and 2 from the 2nd rank. So answer =
13 ! 12 ! C(4,3) ! C(4,2) = 13 ! 12 ! 4 ! 6 = 3,744
Here’s a typical full house
K" K# K\$ 7" 7%
The kings are one of the 13 ranks in the deck. So
there are 13 possibilities for the rank from which 3
cards could be chosen.
The 7’s are one of the remaining 12 ranks.
The 3 kings shown are 3 of the 4 kings.
The 2 sevens shown are 2 of the 4 sevens.
Thus the number of ways of picking a full house is
13 ! 12 ! C(4,3) ! C(4,2) = 13 ! 12 ! 4 ! 6 = 3,744
How many different committees of 3 could
be formed from 8 people? If Jane is one of
the 8 people, how many different
committees could be formed with Jane as a
committee member?
How many different committees of 3 could
be formed from 8 people?
Solution:
C(8,3) = 56 possible committees
How many different committees of 3 could
be formed from 8 people? If Jane is one of
the 8 people, how many different
committees could be formed with Jane as a
committee member?
Solution:
C(8,3) = 56 possible committees
There are C(7,2) = 21 committees possible
with Jane as a member.
Note: You may prefer to think of this as
C(1,1) ! C(7,2)
3 boys and 4 girls have bought tickets for a
row of 7 seats at a movie. In how many
ways can they arrange themselves in the
seats?
— — — — — — —
3 boys and 4 girls have bought tickets for a
row of 7 seats at a movie. In how many
ways can they arrange themselves in the
seats?
— — — — — — —
Solution:
7! = 5040
3 boys and 4 girls have bought tickets for a
row of 7 seats at a movie. In how many
ways can they arrange themselves if the
boys all sit together and the girls sit
together?
— — — — — — —
3 boys and 4 girls have bought tickets for a
row of 7 seats at a movie. In how many
ways can they arrange themselves if the
boys all sit together and the girls sit
together?
B B B G G G G
— — — — — — —
Solution:
3! ! 4! = 144
3 boys and 4 girls have bought tickets for a
row of 7 seats at a movie. In how many
ways can they arrange themselves if the
boys all sit together and the girls sit
together?
B B B G G G G
— — — — — — —
Solution:
3! ! 4! = 144
Answer = 2 ! 144 = 288
3 boys and 4 girls have bought tickets for a
row of 7 seats at a movie. In how many
ways can they arrange themselves if no one
sits beside a person of the same sex?
— — — — — — —