Discrete Mathematics for Computer Science

Counting Principles 427

Hourly 1

Full Service 1

Hourly Full Service 2

Full Service 3

Figure 7.4 Set representation of choices.

The total number of possible choices is just the sum of the number of elements in each

of the disjoint sets. This counting problem is one in which the Addition Principle is used

to find a solution.

The Addition Principle

For a collection of m disjoint sets with nl elements in the first, n2 elements in the

second ... , and nm elements in the mth, the number of ways to choose one element

from the collection is

nl +±n2+'"+nm

As an example, suppose we would like to know the number of elements between

1 and 100 that are divisible by 11 or 13. Setll = 111, 22, 33, 44, 55, 66, 77, 88, 99},

and Setl3 = {13, 26, 39, 52, 65, 78, 911. Since Setall Setl3 = 0, the answer is found by

simply adding together I Setl 1 and I Setl3 I to get 16 as the answer.
Two steps need to be completed before the Addition Principle can be applied. The first
is to verify that the sets being considered are disjoint. This often proves to be more difficult
than you might expect. The second is to count the number of elements in each of the sets
as defined in the first step.

Example 5. How many ways can you choose a 9, a red card with value greater than 9, or
a black card with a value less than 6 from a standard deck of cards? (A standard deck of
cards is defined in Section 3.1. In this example, an Ace is a high card.)

Solution. The choices can be put into three disjoint sets as shown in Figure 7.5 on page

428. The Addition Principle says that there are

4 + 10 + 8 = 22

possible choices. U