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?
•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
Permutations
An r-permutation of a!set
of nfactorial
means
elements is an ordered Ex.
selection
of r
3! = 3∙2∙1
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
matter!
WhereNOT
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? (can digits be
repeated?)
Think of these numbers
as if they were on tiles,
like Scrabble. After you
use a tile, you can’t use
it again.
3  5  4  60
Ex. 8: In how many ways can
9 horses place 1st, 2nd, or 3rd in
a race?
P

504
9 3
Ex. 9: Suppose there are 15 girls
and 18 boys in a class. In how many
ways can 2 girls and 2 boys be
selected for a group project?
15C2
X 18C2 = 16,065