Discrete Mathematics for Computer Science

The Principle of Inclusion-Exclusion 39

L E U

2499 899

101

C

Figure 1.15 Counting liberals and children.

The Principle of Inclusion-Exclusion for Three Sets says that

ILUEUCI=ILI+IEI+ICI-ILAnEI-ILAnCI-IEAnCI+ ILAnE nCI

= 15,000 + 17,500 + 3500 - 10,001 - 2500 - 900 + 1

= 22,600 U

Here, as often happens, there is a different way to count this collection of elements.

First, note that of the 900 people who have children under five years of age and who

earn more than $45,000 a year, only one is a liberal; the other 899 are conservatives. So,

among the 1000 conservatives with children under five years of age, 1000 - 899 = 101

do not earn more than $45,000. There are 15,000 liberals, plus 17,500 - 10,001 = 7499

conservatives making more than $45,000 a year, plus 101 conservatives with children under

five years of age. Therefore, the answer is

15,000 + 7,499 + 101 = 22,600

The Principle of Inclusion-Exclusion is also used to solve problems in number theory.

Before we explain that example, we need to remind ourselves of one fact from number

theory: For 2, 5, and 30, it is clear that 2130 and 5130. Moreover, it is clear that 2.5 =

10130. It is not always true, however, that the product of two divisors of a number is again
       a divisor of the number. For example, 5, 10, and 30 have the property that 5130 and 10130,

but 5. 10 = 50130 is false. What is true is that if m is an integer and both p and q are

primes such that pim and qim, then p. q~m.

Example 8. How many natural numbers between 1 and 30,000,000 (including 1 and
30,000,000) are divisible by 2, 3, or 5?

Solution. Let

Di = {n e- N: 1 < n < 30,000,000 and n is divisible by i}

What is I D 2 U D 3 U D 5 I? The number is difficult to count directly, so we use the Principle

of Inclusion-Exclusion. I D 2 I = 15,000,000, I D3 I = 10,000,000, and I D5 I = 6,000,000.

How about I D 2 n D 3 I? Since 2 and 3 are both prime, an integer n is divisible by both 2

and 3 if and only if n is divisible by 2.3 = 6. So D 2 n D 3 = D 6 , and I D6I = 5,000,000.

Similarly,

I D 2 n D 5 I = I DioI = 3,000,000

I D3 Ds I = I D15I = 2,000,000