Page 414 - Discrete Mathematics and Its Applications

6.1 The Basics of Counting 393

THE SUBTRACTION RULE If a task can be done in either n 1 ways or n 2 ways, then the
number of ways to do the task is n 1 + n 2 minus the number of ways to do the task that are
common to the two different ways.

The subtraction rule is also known as the principle of inclusion–exclusion, especially when
it is used to count the number of elements in the union of two sets. Suppose that A 1 and A 2 are
sets. Then, there are |A 1 | ways to select an element from A 1 and |A 2 | ways to select an element
from A 2 . The number of ways to select an element from A 1 or from A 2 , that is, the number of
ways to select an element from their union, is the sum of the number of ways to select an element
from A 1 and the number of ways to select an element from A 2 , minus the number of ways to
select an element that is in both A 1 and A 2 . Because there are |A 1 ∪ A 2 | ways to select an element
in either A 1 or in A 2 , and |A 1 ∩ A 2 | ways to select an element common to both sets, we have

|A 1 ∪ A 2 |=|A 1 |+|A 2 |−|A 1 ∩ A 2 |.

This is the formula given in Section 2.2 for the number of elements in the union of two sets.
Example 18 illustrates how we can solve counting problems using the subtraction principle.

EXAMPLE 18 How many bit strings of length eight either start with a 1 bit or end with the two bits 00?

Solution: We can construct a bit string of length eight that either starts with a 1 bit or ends
with the two bits 00, by constructing a bit string of length eight beginning with a 1 bit or by
constructing a bit string of length eight that ends with the two bits 00. We can construct a bit
7
string of length eight that begins witha1in2 = 128 ways. This follows by the product rule,
because the first bit can be chosen in only one way and each of the other seven bits can be
chosen in two ways. Similarly, we can construct a bit string of length eight ending with the two
6
bits 00, in 2 = 64 ways. This follows by the product rule, because each of the first six bits can
be chosen in two ways and the last two bits can be chosen in only one way.
1
Some of the ways to construct a bit string of length eight starting with a 1 are the same
7
2 = 128 ways as the ways to construct a bit string of length eight that ends with the two bits 00. There are
5
0 0 2 = 32 ways to construct such a string. This follows by the product rule, because the first
bit can be chosen in only one way, each of the second through the sixth bits can be chosen
6
2 = 64 ways
in two ways, and the last two bits can be chosen in one way. Consequently, the number of
1 0 0
bit strings of length eight that begin witha1orend with a 00, which equals the number
5
2 = 32 ways of ways to construct a bit string of length eight that begins witha1or that ends with 00,
equals 128 + 64 − 32 = 160. ▲
We present an example that illustrates how the formulation of the principle of inclusion–
exclusion can be used to solve counting problems.

EXAMPLE 19 A computer company receives 350 applications from computer graduates for a job planning a
line of new Web servers. Suppose that 220 of these applicants majored in computer science, 147
majored in business, and 51 majored both in computer science and in business. How many of
these applicants majored neither in computer science nor in business?

Solution: To find the number of these applicants who majored neither in computer science nor
in business, we can subtract the number of students who majored either in computer science
or in business (or both) from the total number of applicants. Let A 1 be the set of students who
majored in computer science and A 2 the set of students who majored in business. Then A 1 ∪ A 2
is the set of students who majored in computer science or business (or both), and A 1 ∩ A 2 is the