— Page references correspond to locations of Extra Examples icons in the textbook.
#1. There are three available flights from Indianapolis to St. Louis and, regardless of which of these flights
is taken, there are five available flights from St. Louis to Dallas. In how many ways can a person fly from
Indianapolis to St. Louis to Dallas?
Solution:
There are three ways to make the first part of the trip and five ways to continue on with the second part
of the trip, regardless of which flight was taken for the first leg of the trip. Therefore, by the product rule
there are 3 · 5 = 15 ways to make the entire trip.
#2. A certain type of push-button door lock requires you to enter a code before the lock will open. The
lock has five buttons, numbered 1, 2, 3, 4, 5.
(a) If you must choose an entry code that consists of a sequence of four digits, with repeated numbers
allowed, how many entry codes are possible?
(b) If you must choose an entry code that consists of a sequence of four digits, with no repeated digits
allowed, how many entry codes are possible?
Solution:
(a) We need to fill in the four blanks in
, where each blank can be filled in with any of the five
digits 1, 2, 3, 4, 5. By the generalized product rule this can b e done in 5
4
= 625 ways.
(b) We need to fill in the four blanks in
, but each blank must be filled in with a distinct integer
from 1 to 5. By the generalized product rule that can be done in 5 · 4 · 3 · 2 = 120 ways.
#3. Count the number of print statements in this algorithm:
for i := 1 to n
begin
for j := 1 to n
prin t “hello”
for k := 1 to n
prin t “hello”
end
Solution:
1
Rosen, Discrete Mathematics and Its Applications, 7th edition, Global Edition
Extra Examples
Section 6.1—The Basics of Counting
p.376, icon before Example 1
p.376, icon before Example 1
p.376, icon before Example 1
Show All Solutions
See Solution
See Solution
See Solution
For each value of i,boththej-lo op and k-loop are executed. Thus for each i, the number of print statements
executed is n + n,or2n. Therefore the total number of print statements executed is n · 2n =2n
2
.
#4. Co
unt the number of print statements in this algorithm:
for i := 1 to n
begin
for j := 1 to i
prin t “hello”
for k := i +1to n
prin t “hello”
end
Solution:
For each value of i,boththej-lo op and k-loop are executed. Thus for each i, the number of print statements
executed is i in the first loop plus n − i in the second loop. Therefore, for each i, the numb er of print
statements is i +(n − i)=n.
Therefore the total number of print statements executed is n · n = n
2
.
#1. Find
the number of strings of length 10 of letters of the alphabet, with no repeated letters, that contain
no vowels.
Solution:
The key to solving the problem is keep in mind a row of ten blanks:
.
Each of the ten blanks in the string must contain one of the 21 consonants, with no repeated consonants
allowed. By the extended version of the product rule, the answer is 21 · 20 · 19 ···13 · 12.
#2. Find
the number of strings of length 10 of letters of the alphabet, with no repeated letters, that begin
with a vowel.
Solution:
Keep in mind a row of ten blanks:
.
Therearefivewaysinwhichthefirstletterinthestring can be a vowel. Once the vowel is placed in the first
blank, there are 25 ways in which to fill in the second blank, 24 ways to fill in the third blank, etc. Using
the extended product rule we obtain
5
place
vowel
· 25 · 24 · 23 ···18 · 17
place other
letters
.
2
p.
376, icon before Example 1
p.381, icon at Example 15
p.381, icon at Example 15
See Solution
See Solution
See Solution
#3. Find
the number of strings of length 10 of letters of the alphabet, with no repeated letters, that have
C and V at the ends (in either order).
Solution:
Using a row of ten blanks, we first count the number of ways to have the pattern
C
V .
The number of ways to fill in the eight interior letters is 24 · 23 ···18 · 17.
Similarly, the number of words of the form
V
C
is 24 · 23 ···18 · 17.
Therefore, by the sum rule the answer is (24 · 23 ···18 · 17) + (24 · 23 ···18 · 17) = 2(24 · 23 ···18 · 17).
#4. Find
the number of strings of length 10 of letters of the alphabet, with repeated letters allowed, that
have vowels in the first two positions.
Solution:
Keep in mind a row of ten blanks:
.
If vowels must be in the first two positions and letters can be repeated, we obtain the product
5 · 5
place 2
vowels
· 26 · 26 ····26
place any
8 letters
,
which is 5
2
· 26
8
.
#5. Find
the number of strings of length 10 of letters of the alphabet, with no repeated letters, that have
vowels in the first two positions.
Solution:
Keep in mind a row of ten blanks:
.
We will first count the number of ways to place vowels in the first two blanks. We can choose any of the five
vowels for the first blank and any of the remaining four vowels to put in the second blank. Because we must
do both, there are 5 · 4 = 20 ways to place the two vowels.
Next we will place eight of the remaining 24 letters in the remaining eight blanks. This can be done in
24 · 23 ···18 · 17 ways.
3
p.
381, icon at Example 15
p.381, icon at Example 15
p.381, icon at Example 15
See Solution
See Solution
See Solution
Therefore, by the product rule, the number of ways to place vowels in the first two blanks and eight letters
in the remaining eight blanks is
(5 · 4)
place 2
vowels
· (24 · 23 ···18 · 17)
place 8
other letters
.
#6. T
en men and ten women are to be put in a row. Find the number of possible rows.
Solution:
Keep in mind a row of twenty blanks. There is no restriction on how the men and women can be placed in
arow,sotheansweris20· 19 · 18 ···3 · 2 · 1 = 20!.
#7. T
en men and ten women are to be put in a row. Find the number of possible rows if no two of the
same sex stand adjacent.
Solution:
Keep in mind a r ow of twenty blanks. If no two of the same sex stand in adjacent positions, then there are
two possible patterns, using M for male and F for female:
MFMFMFMFMFMFMFMFMFMF and FMFMFMFMFMFMFMFMFMFM.
We will count the number of ways of achieving the first pattern and double this number to find the final
answer. The first man can be chosen in 10 ways, the first woman can be chosen in 10 ways, the second man
can be chosen in 9 ways, etc. Thus, by the extended product rule, each pattern can be obtained in
10
place
first
man
· 10
place
first
woman
· 9
place
second
man
· 9
place
second
woman
··· 2
place
ninth
man
· 2
place
ninth
woman
· 1
place
tenth
man
· 1
place
tenth
woman
or (10 · 9 ···2 · 1)
2
ways. The second pattern can be obtained in the same number of ways, so we double the
answer to get 2(10 · 9 ···2 · 1)
2
=2· 10!
2
.
#8. Ten men and ten women are to be put in a row. Find the number of possible rows if Beryl, Carol, and
Darryl want to stand next to each other in some order (such as Carol, Beryl, and Darryl, or Darryl, Beryl,
and Carol).
Solution:
Keep in mind a row of twenty blanks.
We first consider the arrangements where Beryl, Carol, and Darryl stand next to each other in that order.
We begin by putting the 17 other people in a row, which can be done in 17! ways. No matter how the 17
4
p.
381, icon at Example 15
p.381, icon at Example 15
p.381, icon at Example 1 5
See Solution
See Solution
See Solution
areplacedinarow,Beryl,Carol,andDarrylcaneither be inserted (in that order) between two of the 17,
or else placed at one of the two ends. This is pictured in the following diagram, where the 17 x’s represent
the 17 people placed in a row. There are 18 places in which Beryl, Carol, and Darryl can b e placed together
— 16 places between the x’s and two places on the two ends — marked by blanks.
x x x x x x x x x x x x x x x x x
Therefore, the number of ways to place the 18 people, with Beryl, Carol, and Darryl next to each other (in
that order) is
17!
place
other 17
· 18
spots
for B,C,D
.
But Beryl, Carol, and Darryl can be permuted in 3! ways. Therefore, the final answer is 17! · 18 · 3!.
#1. Find the number of integers from 1 to 400 inclusive that are:
(a) divisible by 6.
(b) not divisible by 6.
Solution:
(a) Every sixth integer from 1 to 400 is divisible by 6, yielding
400
6
= 66. (Note: When we divide 400
by 6 we obtain 66 2/3. The fraction 2/3 indicates that we are two thirds of the way toward the next integer
divisible by 6, which is 402. We round down because 402 is beyond the range of numbers from 1 to 400.)
(b) From part (a) we know that 66 integers from 1 to 400 are divisible by 6. Hence the number that are not
divisible by 6 is 400 − 66 = 334.
#2. Find the number of integers from 1 to 400 inclusive that are:
(a) divisible by 6 and 8.
(b) divisible by 6 or 8.
Solution:
(a) Divisibility by a and b is the same as divisibility by the least common multiple of a and b. Therefore,
divisibility by 6 and 8 is the same as divisibility by 24. The answer is
400
24
= 16.
(b) We cannot take the number of integers divisible by 6 and add to it the number of integers divisible by 8,
because this would count integers such as 24 or 48 twice (because they are divisible by both 6 and 8). We
need to use the inclusion-exclusion principle to avoid the “double counting”.
Let A
1
= {x | 1 ≤ x ≤ 400,xis divisible by 6} and A
2
= {x | 1 ≤ x ≤ 400,xis divisible by 8}.Wewant
|A
1
∪ A
2
|. By the inclusion-exclusion principle we have
|A
1
∪ A
2
|= |A
1
| + |A
2
|−|A
1
∩ A
2
|
=
400
6
+
400
8
−
400
24
5
p.
p.
38
383, icon at Example 18
3, icon at Example 18
See Solution
See Solution
=66+50− 16
= 100.
Note: When the word “or” a ppears in a counting problem, it is a wise strategy to consider using the
inclusion-exclusion principle.
#3. Find the number of strings of length 10 of letters of the alphabet, with repeated letters allowed,
(a)thatbeginwithCandendwithV.
(b) that begin with C or end with V.
Solution:
(a) Keep in mind a row of ten blanks:
.
If the string has the form
C
V ,
there are 26 ways to fill in each of the eight intermediate blanks. Hence there are 26
8
strings of this form.
(b) We need to count the number of strings that have the form
C
or V
The number of strings of each form is 26
9
. However, we cannot simply add the two numbers to get our
answer. If we do this, we are counting the number of strings of the form C
V twice
because each such string fits both patterns.
We need to use the inclusion-exclusion principle to avoid the double-counting. Let A
1
be the set of all strings
of length ten that begin with C and let A
2
be the set of all strings of length ten that end with V. We want
|A
1
∪ A
2
|. But by the inclusion-exclusion principle,
|A
1
∪ A
2
| = |A
1
| + |A
2
|−|A
1
∩ A
2
|
=26
9
+26
9
− 26
8
.
(The term 26
8
was obtained as the size of A
1
∩ A
2
, which is the set of all strings of length ten that b egin
withCandendwithV.)
6
p.
383, icon at Example 18
See Solution
