Transcript Permutations and Combinations

MATH 1107
Elementary Statistics
Lecture 7
Combinations and Permutations
Combinations and Permutations
You have lost your debit card. Assuming that your
signature cannot be forged, and the thief tries to
discover your PIN, how many combinations will he
have to try?
Most PIN-based cards, have 4 digit PINs. Assuming
that each number (0-9) can be used in each
position, there are 10*10*10*10 or 104 or 10,000
different ways. This is an example of the
fundamental counting rule. The answer is Mn,
where M is the number of possibilities of an event
and n is the number of events.
Combinations and Permutations
How many different ways can a student answer all the
questions on a true-false test with 20 questions?
The answer is 220 or 1,048,576 different ways. In
other words, the probability of getting the right
answer at random is 1/1,048,576.
Combinations and Permutations
You are having a sit-down dinner with 10 people. How
many different ways can you arrange the seating at a
single table?
This is called a permutation problem – The answer
is (n)*(n-1)*(n-2)*(n-3)…or n!. In this problem,
the answer is 10! or 10*9*8*7*6*5*4*3*2*1 or
3,628,800.
Combinations and Permutations
Now, what if you only have 8 chairs? How many
different ways can you seat 10 people with 8 chairs (2
people will have to sit on the floor or stand)?
This too is a permutation problem – with n distinct
objects taken r at a time. In this instance, we have
10 objects (people) taken 8 at a time:
nPr
= n!/(n-r)!
Combinations and Permutations
So, we have 10 people (n) taken 8 at a time ®…
10!/(10-8)! = 3,628,800/2 or 1,814,400
Combinations and Permutations
The Liberals for Bush club as 24 members. If four
names are selected from a hat to represent the four
officers of the club, how many different ways can this
be done?
In this instance, we have 24 objects or people (n)
taken 4 at a time (r) :
n!/(n-r)! = 24!/(24-4)! or 24!/20! = 24*23*22*21
= 255,024.
Combinations and Permutations
How many different permutations are there of the
letters in the word “book”?
This question can be approached two ways…
If we determine that the first “o” and the second
“o” are unique letters, then we treat the problem as
a factorial problem – n! or 4*3*2*1 = 24.
Combinations and Permutations
However, if we determine that the two “o”s are not
different (order does not matter), then the approach
is slightly different. There will be fewer possibilities,
if we do not discriminate between the “o”s –
n!/(n1!*n2!*n3!)
Specifically, in this case, we have 4 letters (n), 1 b
(n1), 1 k (n2) and 2 o (n3)…
4!/(1!*1!*2!) = 24/2 = 12.
Combinations and Permutations
Notice that in all of the previous problems, different
orderings counted (BOOK is different from KOOB).
When different orderings of the same events are
counted separately, we have a permutation.
Alternatively, when orderings of the same events
are not counted separately, we have a
combination. In a combination, BOOK is
considered to be the same as KOOB.
Combinations and Permutations7
In how many different ways can a person gathering
data for a market research firm select 3 of 20
households in an apt complex for interviewing?
In this instance, we don’t care what order the
households are selected (1,2,3 is the same as
3,2,1). So the formula is slightly different:
nCr
= n!/r!(n-r)!
Combinations and Permutations
So, we have 20 households (n) taken 3 at a time (r)
…
20!/3!(20-3)! = 1,140
Remember that there will ALWAYS be fewer
possible combinations than permutations!