Transcript Permutations

Aim: Is Spiderman a permutation or
what?
A = {a, b, c, d, e}
What could be a two element subset of A?
Is {a, b} = {b, a} ?
Yes
order of elements in set is not important
Aim: Permutations
Course: Math Lit..
Subsets & Arrangements
A = {a, b, c, d, e}
If order were important
is {a, b} = {b, a} ?
No
If the two elements a and b are selected from A,
then
there is one subset (order not important): {a, b}
there are two arrangements (order important):
(a, b) and (b, a)
note: both are selected without repetitions
(without replacement)
Aim: Permutations
Course: Math Lit..
Model Problem
Consider selecting the elements a, b, and c
from set A = {a, b, c, d, e}. List all possible
subsets of these elements, as well as all
possible arrangements.
1 subset: {a, b, c}
6 arrangements: (a, b, c),
(a, c, b), (b, a, c), (b, c, a),
(c, a, b), (c, b, a)
Aim: Permutations
a
b
c
b
c
c
a
b
c
c
a
a
b
b
a
Course: Math Lit..
Counting Principle at Work
Tom,
Dick,
Harry,
Mary
Larry
& Joe
How many different arrangements can be
made using all six names?
w/o repetition
6 • 5 • 4 • 3 • 2 • 1 = 720
6 ways 5 ways 4 way 3 ways
to
to
to
to
choose choose choose choose
1st
2nd
3rd
4th
name name name name
2 ways
to
choose
5th
name
1 way
to
choose
6th
name
How many different arrangements can be
made using 9 names?
9 • 8 • 7 • 6 • 5 • 4 • 3 • 2 • 1 = 362,880
Factorial: n! = n•(n - 1)(n - 2)(n - 3). . . . 1.
Aim: Permutations
Course: Math Lit..
When arranging all objects
in the set
Counting Principle at Work
Tom,
Dick,
Harry,
Mary
Larry
& Joe
How many different arrangements using
only 3 names can be made from six names?
6 • 5 • 4 = 120
6 ways 5 ways 4 ways
to
to
to
choose choose choose
1st
2nd
3rd
name name name
Since our
selection is limited
to only 3 names
we stop after the
3rd selection
How many different arrangements using 6
names from a selection of 9 names?
9 • 8 • 7 • 6 • 5 • 4 = 60480
How many three letter ‘words’ can be made
Aim: Permutations
from the
word ‘STUDY’? 5 Course:
• 4 •Math
3 Lit..= 60
Permutations
A permutation is an arrangement of objects
in a specific order.
The number of permutation of n things
taken n at a time is
nPn
= n! = n(n – 1)(n – 2)(n – 3) . . . 3, 2, 1
The number of permutation of n things
taken r at a time is
n
Pr  n(n  1)(n  2)L
r factors
n!

( n  r )!
Factorial: n! = n•(n - 1)(n - 2)(n - 3). . . . 1.
When arranging all objects in the set:
Aim: Permutations
Definition - 0! = 1.
Course: Math Lit..
Model Problems
5P5
= n! = 5 • 4 • 3 • 2 • 1 = 120
8P6
=
n! = 8!
= 8!
(n - r)!
(8 - 6)!
2!
8•7•6•5•4•3•2•1
2•1
6P1
= 20160
= 6! = 6
5!
How many three letter ‘words’ can be
made from the letters of
3P3
CAT
GOAT
= 6
4P3
CLONE
Aim: Permutations
5P3
= 24
= 60
Course: Math Lit..
Model Problems
How many arrangements can be made
from the word ANGLE?
5P5
= 120
Repetition is key issue
How many arrangements can be made
from the word ANGLE if repetition of
letters is allowed?
5 • 5 • 5 • 5 • 5 = 55 = 3125
How many 5-letter arrangements can be
made from E, Q, B, X, R, T, L, A, and V if the
last two letters must be vowels.
no repetition
7 • 6 • 5 • 2 • 1 = 420
Aim: Permutations
Course: Math Lit..
Repetitions
How many 3-letter
arrangements can
you make from the
word TEA?
TEA
EATA
TETA
EETA
AET
6
How many 3-letter
arrangements can
you make from the
word TEE?
TEE
EET
ETE
3 TEE
Duplicates ETE
EET
Repeated letters alter number of
arrangements possible because
they lead to duplicated ‘words’.
Aim: Permutations
Course: Math Lit..
Permutations with Repetitions
The number of permutations of n things,
taken n at a time with r of these things
identical, is given by
n ! n Pn

r!
r!
How many 3-letter arrangements can
you make from the word TEE?
n = 3 letters to arrange
r = 2, the number of
times E is repeated
Aim: Permutations
3!
=3
2!
Course: Math Lit..
Permutations with Repetitions
The number of permutations of n things,
taken n at a time with r things identical,
s things identical, and t things identical,
is given by
n!
r ! s! t!
Find the number of permutations of the
letters in MISSISSIPPI.
n = 11 letters to arrange
r = 4, the number of times I is repeated
s = 4, the number of times S is repeated
s = 2, the number of times P is repeated
11!
=
34,650
4! 4! 2!
Aim: Permutations
Course: Math Lit..
Model Problems
How many different 5-letter permutations
are there is the letters in
APPLE
ADDED
VIVID
5!
= 60
2!
5!
= 20
3!
5!
= 30
2! 2!
n!
r ! s! t!
How many different 5-digit numerals
can be written using all 5 digits listed?
1, 2, 3, 4, 5
5! = 120
1, 1, 2, 2, 2
5!
= 10
3! 2!
Aim: Permutations
Course: Math Lit..
Model Problems
How many 5-letter arrangements can be
made from E, Q, B, X, R, T, L, A, and V if the
last two letters must be vowels.
no repetition
9 letters altogether; A and E are only vowels;
 7 consonants for 1st three events
Counting
Principle
Permutations
n!
n Pr 
( n  r )!
7 · 6 · 5 · 2 · 1
E1 E2 E3
E4 E5
P3
7!
(7  3)!
·
210
·
Aim: Permutations
7
= 420
·
2
P2
2!
2
Course: Math Lit..
= 420
Model Problems
Sea-going vessels use different flags or
arrangements of flags to send messages to
other vessels. If 10 different flags are
available, and if every message consists of
three different flags, how many different
messages are possible?
10P3
How messages are possible if the top flag
must be one of three specific
3 • 9 • 8 = 216
flags?
How many different ways can John place a
math book, a history book, a science book
and an art book on a shelf? 4P4 = 4! = 24
How many different ways can John place
the 4 books if the math book must be first?
Aim: Permutations
1 Course:
• 3 •Math
2 Lit..
= 6
Model Problems
Tell how many four letter ‘words’ can be
made from the letters X, B, T, L, R, V, and A
for each situation.
n!
A. There are no restrictions n Pr 
( n  r )!
7!
7! 7  6  5  4  3  2  1


7 P4 
(7  4)! 3!
3  2 1
 7  6  5  4  840
B. The first letter must be A
1 •
ONLY 1
CHOICE
FOR FIRST
Aim: Permutations
LETTER - A
6P3
= 120
AFTER THE A IS
PLACED, THERE
ARE 6 LETTERS
Course: Math Lit..
LEFT
FOR 3
PLACES OR 6P3
Model Problems
Tell how many four letter ‘words’ can be
made from the letters X, B, T, L, R, V, and A
for each situation.
C. The third letter must be A
6 • 5 • 1 • 4 = 120
ONLY 1
CHOICE
FOR THIRD
LETTER - A
AFTER THE A IS PLACED, THERE
ARE 6 LETTERS LEFT FOR 3
PLACES OR 6P3
1 • 6P3
Aim: Permutations
= 120
Course: Math Lit..
Model Problems
Tell how many four letter ‘words’ can be
made from the letters X, B, T, L, R, V, and A
for each situation.
D.. The last two letters must be R or T in
either order
5 • 4 • 2 • 1 = 40
ONLY 2 CHOICES
FOR THIRD LETTER
& FOURTH LETTER
AFTER THE R AND T ARE
PLACED, THERE ARE 5 LETTERS
LEFT FOR 2 PLACES OR 5P2
5P2
Aim: Permutations
•2•1
= 40
Course: Math Lit..
Model Problem
Using the word SQUARE, find how many
6-letter arrangements with no repetitions are
possible if the:
A. First letter is S
1 • 5 • 4 • 3 • 2 • 1 = 120
ONLY 1
CHOICE FOR
FIRST
LETTER - S
Aim: Permutations
5P5
AFTER THE S IS
PLACED, THERE
ARE 5 LETTERS
LEFT FOR 5
PLACES OR 5P5
Course: Math Lit..
Model Problem
Using the word SQUARE, find how many
6-letter arrangements with no repetitions are
possible if the:
B. Vowels and consonants
alternate beginning with a
VOWELS - U, A, E
vowel
CONSON. - S, Q R
3 • 3 • 2 • 2 • 1 •1
ONLY 3
CHOICES
S,Q,R
ONLY 3
CHOICES
U,A,E
3P3
Aim: Permutations
= 36
•
3P3
= 36
Course: Math Lit..
Model Problems
Four different biology books and three
different chemistry books are to be placed
on a shelf with the biology books together
and to the right of the chemistry books. In
how many ways can this be done?
AMDKD
LK3EW
AMDKD
LK3EW
AMDKD
LK3EW
AMDKD
LK3EW
AMDKD
LK3EW
AMDKD
LK3EW
AMDKD
LK3EW
3 • 2•1•4•3•2•1
First three
books are
chemistry
= 144
Last four
books are
biology
3P3
4P4
3P3
Aim: Permutations
•
4P4
= 144
Course: Math Lit..
Model Problem
Frances has 8 tulip bulbs, 10 daffodil bulbs,
and 28 crocus bulbs. In how many
different ways can Frances plant these
bulbs in a row in her garden?
n!
r ! s! t!
n = # bulbs = 46
r = # of tulips = 8
s = # of daffodils = 10
t = # of crocus = 28
46!
= 1.233. . . x 1017
8! 10! 28!
Aim: Permutations
Course: Math Lit..
Model Problems
A combination lock has 60 numbers around its
dial. How many different arrangments are
possible if every combination has three numbers?
Question: can a number be used
more than once?
60 • 60 • 60
= 216,000
A three digit number is formed by selecting
from the digits 4, 5, 6, 7, 8, and 9 with no
repetitions. How many of these 3-digit
numbers will be greater than 700?
3•5•4
ONLY 3
CHOICES
Aim:FOR
Permutations
FIRST
DIGIT 7,8,9
= 60
5P2
Course: Math Lit..
Model Problem
Find the total number of different twelveletter arrangements that can be formed
using the letters in the word
PENNSYLVANIA.
Aim: Permutations
Course: Math Lit..
Aim: Permutations
Course: Math Lit..
Aim: Permutations
Course: Math Lit..