258
Sets, Combinatorics, and Probability
outcomes at any one level of the tree is the same throughout that level. In
Figure 4.4, for example, level 2 of the tree shows two outcomes for each of the
3 branches formed at level 1. Less regular decision trees can still be used to solve
counting problems where the multiplication principle does not apply.
example 39
Tony is pitching pennies. Each toss results in heads (H) or tails (T). How many
ways can he toss the coin 5 times without having 2 heads in a row?
T
H
T
T
T
H
H
T
H
T
H
H
T
H
T
T
H
T
T
T
H
H
T
T
H
T
H
T
T
T
T
H
T
T
T
H
T
T
H
T
T
H
T
H
T
H
T
T
H
T
T
T
H
T
T
T
H
H
T
T
T
H
T
T
H
T
H
T
T
H
T
T
T
T
T
T
H
T
T
T
H
T
T
T
T
T
T
H
T
T
T
H
H
T
H
T
Toss 1
Toss 2
Toss 5
Toss 4
Toss 3
Figure 4.5 shows the decision tree for this problem. Each coin toss has 2 outcomes;
the left branch is labeled H for heads, the right branch is labeled T for tails. Whenever an H appears on a branch, the next level can only contain a right (T) branch.
There are 13 possible outcomes, shown at the bottom of the tree.
figure 4.5
■
PraCtiCe 24 Explain why the multiplication principle does not apply to Example 39.
■
PraCtiCe 25 Draw the decision tree for the number of strings of X ’s, Y ’s, and Z ’s with length 3 that do
not have a Z following a Y.
S e c t i o n 4 . 2 review
tecHniQue
• Use the multiplication principle, the addition principle, and decision trees for counting the number of
objects in a finite set.
main iDeaS
• The multiplication principle is used to count
the number of possible out comes for a sequence of
events, each of which has a fixed number of outcomes.
• The addition principle is used to count the number
of possible outcomes for disjoint events.
• The multiplication and addition principles are often
used together.
• Decision trees can be used to count the number
of outcomes for a sequence of events where the
number of outcomes for a given event is not constant but depends on the outcome of the preceding event.
W