Transcript Counting, Permutations, & Combinations

Counting,
Permutations, &
Combinations
A counting problem asks
“how many ways” some
event can occur.
Ex. 1: How many three-letter codes are
there using letters A, B, C, and D if no
letter can be repeated?
• One way to solve is to list all
possibilities.
Ex. 2: An experimental psychologist uses
a sequence of two food rewards in an
experiment regarding animal behavior.
These two rewards are of three different
varieties. How many different sequences
of rewards are there if each variety can be
used only once in each sequence?
Next slide
•Another way to solve is a factor
tree where the number of end
branches is your answer.
b
a
c
a
b
c
a
c
b
Fundamental Counting Principle
Suppose that a certain procedure P can be
broken into n successive ordered stages, S1,
S2, . . . Sn, and suppose that
S1 can occur in r1 ways.
S2 can occur in r2 ways.
Sn can occur in rn ways.
Then the number of ways P can occur is
r1  r2    rn
Ex. 2: An experimental psychologist uses
a sequence of two food rewards in an
experiment regarding animal behavior.
These two rewards are of three different
varieties. How many different sequences
of rewards are there if each variety can
be used only once in each sequence?
Using the fundamental counting principle:
3
1st reward
X
2
2nd reward
! means factorial
Ex. 3! = 3∙2∙1
Permutations
An r-permutation of a set of n
elements is an ordered selection of r
elements from the set of n elements
0! = 1
n!
n Pr 
n  r !
Ex. 1:How many three-letter
codes are there using letters A, B,
C, and D if no letter can be
repeated?
Note: The order does matter
4!
 24
4 P3 
1!
Combinations
The number of combinations of n
elements taken r at a time is
n!
n Cr 
r!n  r !
Order does
NOT matter!
Where n & r are nonnegative integers & r < n
Ex. 3: How many committees of
three can be selected from four
people?
Use A, B, C, and D to represent the people
Note: Does the order matter?
4!
4
4 C3 
3!1!
Ex. 4: How many ways can the
4 call letters of a radio station
be arranged if the first letter
must be W or K and no letters
repeat?
2  25  24  23  27,600
Ex. 5: In how many ways can
our class elect a president, vicepresident, and secretary if no
student can hold more than one
office?
n
P3 
Ex. 6: How many five-card hands
are possible from a standard deck
of cards?
52
C5  2,598,960
Ex. 7: Given the digits 5, 3, 6, 7, 8,
and 9, how many 3-digit numbers
can be made if the first digit must
be a prime number, and the last
digit must be an odd number?
3  5  4  60
Think of these numbers
as if they were on tiles,
like Scrabble. After you
use a tile, you can’t use
it again.
Ex. 8: In how many ways can
9 horses place 1st, 2nd, or 3rd in
a race?
9
P3  504
Ex. 9: In how many ways can
a team of 9 players be selected
if there are 3 pitchers, 2
catchers, 6 in-fielders, and 4
out-fielders?
3
C1  2 C1  6 C4  4 C3  360