Page 416 - Discrete Mathematics and Its Applications

6.1 The Basics of Counting 395

Winning team
shown in color Team 2 Team 1

Game 1

Game 2
Team 2
Team 1
Team 2
Team 1
Game 3
Team 1
Team 2
Team 2
Team 1
Team 2
Team 1
Team 2
Team 1
Game 4
Team 2
Team 1
Team 2
Team 2
Team 1
Team 1
Game 5
Team 1
Team 1
Team 2
Team 2
Team 2
Team 1
Team 2
Team 2
Team 1
Team 1
Team 1
Team 2
Team 1
Team 2
Team 2
Team 2
Team 1
Team 1
FIGURE 3 Best Three Games Out of Five Playoffs.
EXAMPLE 21 How many bit strings of length four do not have two consecutive 1s?
Solution: The tree diagram in Figure 2 displays all bit strings of length four without two con-
secutive 1s. We see that there are eight bit strings of length four without two consecutive 1s. ▲
EXAMPLE 22 A playoff between two teams consists of at most five games. The first team that wins three games
wins the playoff. In how many different ways can the playoff occur?
Solution: The tree diagram in Figure 3 displays all the ways the playoff can proceed, with the
winner of each game shown. We see that there are 20 different ways for the playoff to occur. ▲
EXAMPLE 23 Suppose that “I Love New Jersey” T-shirts come in five different sizes: S, M, L, XL, and XXL.
Further suppose that each size comes in four colors, white, red, green, and black, except for XL,
which comes only in red, green, and black, and XXL, which comes only in green and black. How
many different shirts does a souvenir shop have to stock to have at least one of each available
size and color of the T-shirt?
Solution: The tree diagram in Figure 4 displays all possible size and color pairs. It follows that
the souvenir shop owner needs to stock 17 different T-shirts. ▲
W = white, R = red, G = green, B = black

S M L XL XXL

W RG B W RG B W RG B RG B G B

FIGURE 4 Counting Varieties of T-Shirts.