Chapter 8
COUNTING PRINCIPALS,
PERMUTATIONS, AND
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.
ABC ABD ACB ACD ADB ADC
BAC BAD BCA BCD BDA BDC
CAB CAD CBA CBD CDA CDB
DAB DAC DBA DBC DCA DCB
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
Count thetree where
number the to
of branches
determine the number of ways.
number of end branches is
your answer. b
a c
a
b c
There are six a
different ways to
c
give the rewards. 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 Revisited: 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 X 2
1st reward 2nd reward
PERMUTATIONS
An r-permutation of a set of n elements
! means factorial
is an ordered selection of r elements
Ex. 3! = 3∙2∙1
from the set of n elements
n!
n Pr
n r !
0! = 1
Ex. 1 Revisited: 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!
4 P3 24
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!
4C3 4
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 a class of
25 students elect a president, vice-
president, and secretary if no student
can hold more than one office?
25 P3 13,800
Ex. 6: How many five-card hands are
possible from a standard deck of cards?
52 C 5 2,598,960
Ex. 7: In how many ways can 9
horses place 1st, 2nd, or 3rd in a race?
P
9 3 504
Ex. 8: 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 × 18C2 = 16,065
IT’S TIME TO
COMBINE & EXPAND
From a group of 7 men and 6 women, five people are to be selected to
form a committee so that at least 3 men on the committee. In how
many ways can it be done?
• What are the possible scenarios
• 3 men and 2 women, 4 men and 1 woman, or 5 men
• (7C3 x 6C2) + (7C4 x 6C1) + (7C5) - but why do we add here?
• (525 + 210 + 21)
• 756
MORE EXAMPLES
In how many different ways can the letters of the word 'LEADING' be
arranged in such a way that the vowels always come together?
• The word 'LEADING' has 7 different letters.
• But, when we pair all the vowels together (EAI) they count as
1 letter
• So there are 5 letters → 5! = 120 combinations
• But the vowels can also be rearranged, so → 3! = 6
• When we combine these two we get 120 x 6 = 720 possible
solutions
CONTINUED
In how many different ways can the letters of the word 'DETAIL' be arranged
in such a way that the vowels occupy only the odd positions?
• There are 6 letters in the given word, out of which there are 3
vowels and 3 consonants.
Let us mark these positions as under:
(1) (2) (3) (4) (5) (6)
• Now, 3 vowels can be placed at any of the three places marked 1,
3, 5.
Number of ways of arranging the vowels = 3P3 = 3! = 6.
• Also, the 3 consonants can be arranged at the remaining 3
positions.
Number of ways of these arrangements = 3P3 = 3! = 6.
• Total number of ways = (6 x 6) = 36.
