Transcript Notes: Permutations and Combinations

Permutations, Combinations,
and Counting Theory
AII.12 The student will compute and
distinguish between permutations and
combinations and use technology for
applications.
Fundamental Counting
Principle

The Meal Deal at Bananabee’s
allows you to pick one appetizer, one
entrée, and one dessert for $10.99.
How many different Meal Deals
could you create if you have three
appetizers, six entrées, and four
desserts to choose from?
Fundamental Counting
Principle
Does your choice of appetizer have
an impact your choice of entrée or
dessert?
 Does your choice of dessert impact
your other choices?
 In the grand scheme of things – NO.
They are INDEPENDENT events –
the outcome of one choice does not
change the other choices.

Fundamental Counting
Principle
The FCP says if one decision can be
made n ways and another can be
made m ways, then the two
decisions can be made nm ways.
 In other words, to determine the
number of ways independent events
can happen together, find the
product of the ways each event can
happen.

Fundamental Counting
Principle
A student is to flip a coin and roll a
die. How many possible outcomes
will there be?
 Does flipping a coin effect the roll of
a die or vice versa?
 NO! Thus they are independent
events.

Fundamental Counting
Principle
A student is to flip a coin and roll a
die. How many possible outcomes
will there be?
 How many outcomes when you flip a
coin?
 2 (heads or tails)
 How many outcomes when you role
a die?
 6 (1, 2, 3, 4, 5, or 6)

Fundamental Counting
Principle
Thus the total number of outcomes
is …
 2 ● 6 = 12
 H1 H2 H3 H4 H5 H6
T1 T2 T3 T4 T5 T6

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?
There are four independent events
(when you don’t consider fashion sense) :
choice of slacks, choice of shirts, choice
of shoes, choice of ties.
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?
 Thus the total number of outfits
(outcomes) is:
4●3●2●5=
 120 possible outfits

Fundamental Counting
Principle
The Meal Deal at Bananabee’s
allows you to pick one appetizer, one
entrée, and one dessert for $10.99.
How many different Meal Deals
could you create if you have three
appetizers, six entrées, and four
desserts to choose from?
 So, how many Meal Deals are
possible?
 72!

Does Order Matter?

How four people finish a race

Picking people for a committee

Arranging letters to create words

Seating students in desks

Picking two of five desserts

Picking the starters for a game

Answering quiz questions
Permutations

A permutation is an arrangement of
items in a particular order, where items
cannot be repeated.
◦ Examples:
 Find the number of ways a certain number of people can
‘place’ in a race (we all want to be first!).
 Creating a password (mix up the numbers/letters and
you aren’t getting in!)
 Assigning titles/positions to people (you can’t be the
president and treasurer!)
Remember, with a permutation, ORDER
MATTERS!!
 To find the number of permutations of n
items we can use the Fundamental
Counting Principal or factorials.

Permutations – order matters
There are 8 acts in a talent show. Each
act would prefer to be close to the start
of the show. How many permutations
are there for their order in the show?
8 ● ___
7 ● ___
6 ●___
5 ● ___
4 ● ___
3 ● ___
2 ●___
1
___
How many ways can you pick the 1st act?
How many ways can you pick the 2nd act?
The total number of ways the acts
can
rd
How many ways can you pick the 3 act?
be ordered
is pattern
40,320. to find the total
Continue
this
number of ways to order the acts in the
talent show.
Factorial
To find the number of outcomes of 8
items in 8 positions, we multiplied
8●7●6●5●4●3●2●1
 This is 8! (8 factorial)
 To find a factorial, multiply the
given number by all the whole
numbers less than it down to 1.
 5! = 5 ● 4 ● 3 ● 2 ● 1 = 120
 Note 0! = 1

Permutations – order matters
Twelve acts applied to be in the talent
show, but time constraints only allow
for eight acts. How many
permutations of eight acts are possible
in the talent show line up?
___
12 ●___
11 ● ___
10 ●___
9 ● ___
8 ● ___
7 ● ___
6 ●___
5
= 19,958,400
How is this problem different from the
last?
Permutations – order matters
12 ●___
11 ●___
10 ●___
9 ●___
8 ●___
7 ● ___
6 ●___
5
___
The Fundamental Counting Principle
is in use with permutations. Each
place in the order is an independent
event. Take the ‘ways’ each place can
occur and multiply them to find the
total number of outcomes. That is the
Fundamental Counting Principle.
Permutations - Official Formula

To find the number of Permutations of
n items chosen r at a time, you can use
the formula:
n!
P 
where 0  r  n
n r (n  r )!

In the first problem, there were 8 acts
and 8 places:
8!
8! 8!
   8!  40,320
8 P8 
(8  8)! 0! 1
Permutations - Official Formula
n!
n pr  ( n  r )! where 0  r  n .
 In the first problem, there were 12 acts
and 8 places:
12!
12!


12 P8 
(12  8)! 4!
12  11  10  9  8  7  6  5  4  3  2  1

4  3  2 1
12  11  10  9  8  7  6  5  19,958, 400
Permutations – order matters
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?
Answer Now
30!
30!

 30 • 29 • 28  24,360
30 P3 
(30  3)! 27!
Permutations – order matters



But what if you could repeat numbers?
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 if numbers can be repeated?
This is no longer a permutation –
orders still matters, but items can be
repeated. You MUST use the FCP for
this question.
FCP – items can repeat
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
if numbers can be repeated?
Answer Now
___  ___  ___  30  30  30  27,000
Permutations – order matters

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?
Answer Now
24!
24!


24 P5 
(24  5)! 19!
24 • 23 • 22 • 21• 20  5,100, 480
Permutations – order matters

There are three students left in the
spelling bee – Arnold, Beth, and
Corrie. Prizes are awarded for first
and second place. How many
different ways can these prizes be
won? Create a list of possibilities.
Permutations – order matters
3●2●1=6
 1st – Arnold, 2nd – Beth
 1st – Arnold, 2nd – Corrie
 1st – Beth, 2nd – Arnold
 1st – Beth, 2nd – Carrie
 1st – Corrie, 2nd – Arnold
 1st – Corrie, 2nd – Beth

Combinations
Arnold, Beth, and Corrie, all work in
the same department. One person
must work on the 4th of July. How
many different ways can the two
people who get the day off be
chosen?
 3 – Arnold and Beth, Arnold and
Corrie, Beth and Corrie.

Combinations
How is this situation similar or
different from the last?
 Similar – choosing two of three
people
 Different – order did not matter, we
were looking for a ‘group’
 Combinations are arrangements of
items where order does not matter.

Combinations – order doesn’t matter

In the Prize problem we listed six
ways to give prizes. But if you
notice, Arnold and Beth were paired
twice, Arnold and Corrie were
paired twice, and Beth and Corrie
were paired twice. If the order did
not matter, we would not need these
repetitions.
Combinations – order doesn’t matter
Combinations are a subset of a
permutation – we just throw out the
repetitions since the order is
irrelevant.
 In the July 4th problem, we had only
3 arrangements. If we take the 6
permutations from the Prize
problem, and divide by 2 (each
pairing happened twice) we get the 3
combinations.

Combinations – order doesn’t matter

To find the number of Combinations
of n items chosen r at a time, you
can use the formula:
n!
C 
where 0  r  n
n r r !(n  r )!

Notice, this is the permutation
formula divided by r! to cancel out
the repetitions.
Combinations – order doesn’t matter

A student must answer 3 out of 5
essay questions on a test. In how
many different ways can the student
select the questions?
Answer Now
5!
5! 5 • 4


 10
5 C3 
3!(5  3)! 3!2! 2 •1
Combinations – order doesn’t matter
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?
Answer Now
52!
52!


52 C5 
5!(52  5)! 5!47!
52 • 51• 50 • 49 • 48
 2,598,960
5 • 4 • 3• 2 •1
Calculator Calculations…
Casio – Run Menu
 OPTN key
 More options (F6)
 PROB (F3)
 Permutation – F2
 Combination – F3
 Factorial – F1
TI – 84
 MATH key
 Arrow over to PRB
 Permutation – 2
 Combination – 3
 Factorial - 4
Calculator Calculations: 7P4
Casio – Run Menu
 Hit the OPTN key
 More options (F6)
 PROB (F3)
 Type the number 7
 Hit F2 for
permutations
 Type the number 4
 Hit EXE
 840
TI – 84
 Type the number 7
 Hit the MATH key
 Arrow over to PRB
 Either arrow down
to #2 or type the
number 2
 Type the number 4
 Hit ENTER
 840
Practice …
How many ways can 8 of 15 students
line up to walk to lunch?
 How many ways can you choose 3 of
10 summer reading books?
 How many ways can pick a three
digit lock code if numbers cannot
repeat?
 How many ways can you pick 2 of 5
lamps for your new living room?

Practice …
How many ways can 8 of 15 students
line up to walk to lunch?
 Permutation; 15P8 = 259,459,200

How many ways can you choose 3 of
10 summer reading books?
 Combination; 10C3 = 120

Practice …
How many ways can pick a three
digit lock code if numbers cannot
repeat?
 Permutation; 10P3 = 720

How many ways can you pick 2 of 5
lamps for your new living room?
 Combination; 5C2 = 10

Challenge …

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?
Answer Now
Challenge …

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:
Center:
Guards:
2!
5! 5  4
4! 4  3
C



10
C


2
C


6
5 2
2
1
4 2
2!3! 2  1
2!2! 2  1
1!1!
2
C1  5 C2  4 C2  2  10  6  120
Thus, the number of ways to select the
starting line up is 120.
Challenge …

A local restaurant is running a
dinner date special. For $24.99 you
can choose 2 of 6 appetizers, 2 of 12
entrées, and 2 of 4 desserts.
Assuming you and your date do not
order the same items, how many
ways could you create a dinner date
special?
Challenge …

A local restaurant is running a dinner date
special. For $24.99 you can choose 2 of 6
appetizers, 2 of 12 entrées, and 2 of 4 desserts.
Assuming you and your date do not order the
same items, how many ways could you create a
dinner date special?
Appetizers:
6!
C

 15
6
2
2!4!
6
Entrées:
12!
 66
12 C2 
2!10!
Desserts:
4!
6
4 C2 
2!2!
C2 • 12 C2 • 4 C2  15 • 66 • 6  5,940
Thus the number of possible meals is 5,940.