Transcript 13.1-13.2 revised Permutations and Combinations

13-1
Permutations and Combinations
The branch of mathematics that studies different possibilities
for the arrangement of objects is
COMBINATORICS
A)
82
B)
42
C)
62
D)
22
B
A)
3
B)
55
C)
45
D)
56
56
Assume that Andrew is scheduling courses for his new
semester. He has a choice of 3 history course, 2 math
courses and 3 science courses. If he has to choose one
course from each area, how many ways can he build his
schedule?
Since the selection of one course does not affect the choice
of a different course, these events are INDEPENDENT
EVENTS.
The classic way to determine the number of possible ways he
can build his schedule would be to make a tree.
Math 1
History 1
Math 2
History 2
Math 1
Math 2
History 3
Math 1
Math 2
Science 1
Science 2
Science 3
Science 1
Science 2
Science 3
Science 1
Science 2
Science 3
Science 1
Science 2
Science 3
Science 1
Science 2
Science 3
Science 1
Science 2
Science 3
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
The Fundamental (or Basic) Counting Principle
If a task consists of a sequence of choices in which there
are p selections for the first choice, q selections for the
second choice, r selections for the third choice, and the
choice for the first selection does not affect the others,
then the task of making these selections can be done in
different ways.
If a license plate consists of a letter,
then 5 numbers, how many different
types of license plates are possible?
license plates
If a license plate consists of a letter, then 5 numbers.
The letter cannot be an E or an F and the last number
must cannot be zero. How many different types of
license plates are possible?
24
10
10
10
2160000
10
9
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?
There are 120 adventures.
A permutation is an arrangement of
objects in a certain order. Order is VERY
important.
The number of permutations possible depends
on the number of objects available (n) and the
number that will be used (r).
Imagine you have 8 children’s books, each with a different title.
How many different ways can they be arranged on a shelf?
Consider the number of choices for each slot.
8
7
6
5
4
3
2
1
Multiply the number of choices for each slot, and that is the
number of possible permutations, that is , the number of
possible different arrangements.
So if you have n distinct items and you plan to use all of them,
you can find the number of possible arrangements (
permutations) by the following multiplication.
n · (n – 1) · (n – 2) · (n – 3) · ... · 1.
This expression is called n factorial, and is written as n!.
5!
5(5-1)(5-2)(5-3)(5-4)
5(4)(3)(2)(1)
 120
How many different arrangements are possible if 4 students are
to be seated in a single row of 4 chairs?
4
4!
3
2
1
If Chloe has 7 different stuffed toys and wants to arrange them
in a line on her bed, but only 3 will fit, how many different
arrangments are possible.
Different problem, How?
One way to find possible permutations is to use the
Fundamental Counting Principle.
First
Toy
7

choices
Second
Toy
6
choices
Third
Toy
5

choices
There are 7 toys.
You are choosing 3
of them in order.
=
210
permutations
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 toys
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.
The number of permutations of n distinct
objects, taken r at a time, is
P
n r
Number of Permutations of n Distinct Objects
The number of different arrangements from selecting r
objects from a set of n objects (r < n), in which
1. the n objects are distinct
2. once an object is used, it cannot be repeated
3. order is important
is given by the formula
n!
P

n r
n  r !
The number of permutations of n objects taken n at a time
n!
n Pn 
n  n !
Surprising?
n
Pn  n!
Evaluate:
10
P3
P
12 3
There are 1320 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.
= 6 • 5 • 4 • 3 = 360
There are 360 ways to select the 4 people.
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.
Permutations in a circle
If n distinct objects are arranged around a circle, then there are
(n-1)!
circular permutations of the objects.
EX:
1. How many different ways can 12 students be placed around a
circular table?
(12-1)! = 11!
2. In how many different ways can 7 appetizers be arranged
around a circular tray?
(7-1)! = 6!
Exception to the circular permutation rule:
1) If the circle contains some sort of a fixed point, the arrangement is
treated as a linear permutation.
Permutations with repetitions
If a group of objects contains a number of identical objects, then the
number of permutations possible can be found by the following
n!
a !b !....etc.
Where a,b, etc. are the number of times each repeating object repeats.
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, consider the 3 letters A,B, and C.,
There are 6 ways to order 3 items, so there are 6 permutations.
6 permutations  {ABC, ACB, BAC, BCA, CAB, CBA}
But they are all the same combination:
1 combination  {ABC}
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.
Because in a combination, different arrangements of the
same items are not counted
The Number of Combinations of n Distinct
Objects Taken r at a Time
The number of different arrangements from
selecting r objects from a set of n objects (r < n),
in which
1. the n objects are distinct
2. once an object is used, it cannot be repeated
3. order is not important
is given by the formula
n!
n Cr 
r!(n  r )!
Evaluate:
10
C3
How many committees of 3 people can be
formed from out of 8 people?
1. the 8 people are distinct
2. once a person is chosen, he/she cannot be
chosen again
3. order is not important
Combinations of 8 taken 3 at a time:
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.
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.
Step 2 Use the formula for combinations.
5
= 495
There are 495 ways to draw 4 cubes from 12.
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?
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.
The swimmers can be selected in 28 ways.
How many committees of 3 people (chair,
secretary, treasurer) can be formed out of 8
people?
1. the 8 persons are distinct
2. once a person is chosen, he/she cannot be
chosen again
3. order IS IMPORTANT
Permutations of 8 taken 3 at a time:
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