Section 5.1: The Basics of Counting: Discrete Mathematics and Its Applications: Page -1

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.1—The Basics of Counting





p.336, icon before Example 1
#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.



p.336, icon before Example 1
#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 be done in 54 = 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.



p.336, icon before Example 1
#3. Count the number of print statements in this algorithm:
for i := 1 to n
begin
for j := 1 to n
print “hello”
for k := 1 to n
print “hello”
end
Solution:

For each value of i, both the j-loop and k-loop are executed. Thus for each i, the number of print statements executed is n + n, or 2n. Therefore the total number of print statements executed is n · 2n = 2n2.





p.336, icon before Example 1
#4. Count the number of print statements in this algorithm:
for i := 1 to n
begin
for j := 1 to i
print “hello”
for k := i + 1 to n
print “hello”
end
Solution:

Solution:
For each value of i, both the j-loop 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 number of print statements is i + (n − i) = n.
Therefore the total number of print statements executed is n · n = n2.



p.340, icon at Example 14
#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.