254
Sets, Combinatorics, and Probability
example 28
When you order pizza at your favorite pizza place, you have the choice of thin
crust, regular crust, or deep-dish; small, medium, or large; and pepperoni, sausage,
barbeque, extra cheese, or vegetable. How many different pizzas can be ordered?
Again, there is a sequence of tasks: choose the crust, choose the size, and
choose the topping. The total number of outcomes is 3 # 3 # 5 = 45.
■
PraCtiCe 22 If a man has four suits, eight shirts, and five ties, how many outfits can he put together?
example 29
For any finite set S, 0 S 0 denotes the number of elements in S. If A and B are finite
sets, then
0 A × B 0 = 0 A 0 # 0 B 0
A × B consists of all ordered pairs with first component from A and second component from B. Forming such ordered pairs can be thought of as the sequence of
tasks of choosing the first component, for which there are 0 A 0 outcomes, and then
choosing the second component, for which there are 0 B 0 outcomes. The result follows from the multiplication principle.
addition Principle
Suppose we want to select a dessert from three pies and four cakes. In how many
ways can this be done? There are two events, one with three outcomes (choosing
a pie) and one with four outcomes (choosing a cake). However, we are not doing a sequence of two events here, since we are getting only one dessert, which
must be chosen from the two disjoint sets of possibilities. The number of different
outcomes is the total number of choices we have, 3 + 4 = 7. This illustrates the
addition principle.
pRinciple additiON PRiNCiPle
If A and B are disjoint events with n 1 and n 2 possible outcomes, respectively, then
the total number of possible outcomes for event “A or B” is n 1 + n 2 .
The addition principle can be extended by induction to the case of any finite
number of disjoint events. (See Exercise 74 at the end of this section.) The addition principle is useful whenever we want to count the total number of possible
outcomes for a task that can be broken down into disjoint cases.
example 30
A customer wants to purchase a vehicle from a dealer. The dealer has 23 autos and
14 trucks in stock. How many selections does the customer have?
The customer wants to choose a car or truck. These are disjoint events; choosing
an auto has 23 outcomes and choosing a truck has 14. By the addition principle,
choosing a vehicle has 23 + 14 = 37 outcomes. Notice the requirement that the
outcomes for events A and B be disjoint sets. Thus, if a customer wanted to purchase a vehicle from a dealer who had 23 autos, 14 trucks, and 17 red vehicles in
stock, we could not conclude that the customer had 23 + 14 + 17 choices!
ReminDeR
Use the addition principle
only when the events are
disjoint—have no common outcomes.
Sets, Combinatorics, and Probability
example 28
When you order pizza at your favorite pizza place, you have the choice of thin
crust, regular crust, or deep-dish; small, medium, or large; and pepperoni, sausage,
barbeque, extra cheese, or vegetable. How many different pizzas can be ordered?
Again, there is a sequence of tasks: choose the crust, choose the size, and
choose the topping. The total number of outcomes is 3 # 3 # 5 = 45.
■
PraCtiCe 22 If a man has four suits, eight shirts, and five ties, how many outfits can he put together?
example 29
For any finite set S, 0 S 0 denotes the number of elements in S. If A and B are finite
sets, then
0 A × B 0 = 0 A 0 # 0 B 0
A × B consists of all ordered pairs with first component from A and second component from B. Forming such ordered pairs can be thought of as the sequence of
tasks of choosing the first component, for which there are 0 A 0 outcomes, and then
choosing the second component, for which there are 0 B 0 outcomes. The result follows from the multiplication principle.
addition Principle
Suppose we want to select a dessert from three pies and four cakes. In how many
ways can this be done? There are two events, one with three outcomes (choosing
a pie) and one with four outcomes (choosing a cake). However, we are not doing a sequence of two events here, since we are getting only one dessert, which
must be chosen from the two disjoint sets of possibilities. The number of different
outcomes is the total number of choices we have, 3 + 4 = 7. This illustrates the
addition principle.
pRinciple additiON PRiNCiPle
If A and B are disjoint events with n 1 and n 2 possible outcomes, respectively, then
the total number of possible outcomes for event “A or B” is n 1 + n 2 .
The addition principle can be extended by induction to the case of any finite
number of disjoint events. (See Exercise 74 at the end of this section.) The addition principle is useful whenever we want to count the total number of possible
outcomes for a task that can be broken down into disjoint cases.
example 30
A customer wants to purchase a vehicle from a dealer. The dealer has 23 autos and
14 trucks in stock. How many selections does the customer have?
The customer wants to choose a car or truck. These are disjoint events; choosing
an auto has 23 outcomes and choosing a truck has 14. By the addition principle,
choosing a vehicle has 23 + 14 = 37 outcomes. Notice the requirement that the
outcomes for events A and B be disjoint sets. Thus, if a customer wanted to purchase a vehicle from a dealer who had 23 autos, 14 trucks, and 17 red vehicles in
stock, we could not conclude that the customer had 23 + 14 + 17 choices!
ReminDeR
Use the addition principle
only when the events are
disjoint—have no common outcomes.