Chapter 13

The Principle of Inclusion and Exclusion

In Chapter 1, we introduced the Addition Principle (AP) which was expressed in terms of sets as follows:

In the statement above, A and B are assumed to be disjoint, written , i.e. A and B have no elements in common. Can we express |A∪B| in terms of |A| and |B| regardless of whether A and B are disjoint? In counting the elements in A∪B, we may first count those in A and then those in B .In doing so, any element in A ∩ B (if there is) is counted exactly twice. Thus, to get the exact count of A ∪ B|, the number A ∩ B| should be deducted. It follows that:

This result can also be seen intuitively with the help of the Venn diagram of Figure 13.1.

Note that (13.1) is a special case of (13.2) as (13.1) follows from (13.2) if we assume that

Identity (13.2) is a simplest form of a principle called the Principle of Inclusion and Exclusion (PIE), which is a very useful and powerful tool in enumeration. First of all, let us show two applications of (13.2).

Example 13.1 Find the number of integers from the set {1,2,…, 1000} which are divisible by 3 or 5.

Figure 13.1

Discussion and Solution The integers which we are looking for are 3, 5, 6, 9, 10, 12, 15, 18, 20, … , 999, 1000. How many are there? Let us try to present the solution more formally, and so we let

It is now clear that our task is to evaluate is the set of numbers in S which are divisible by 3 or 5.

Before applying (13.2) to evaluate |A ∪ B|, we recall a useful notation:

For a real number r, let denote the greatest integer that is smaller than or equal to r.

Thus and so on.

How many integers in {1, 2,…, 10} are there which are divisible by 3? There are three (namely, 3, 6, 9) and note that “three” can be expressed as The number of integers in {1,2,…, 10} which are divisible by 5 is two (namely, 5, 10) and note that “two” can be expressed as

Indeed, in general:

For any two natural numbers n, k with k ≤ n, the number of integers in the set {1,2,…, n} which are divisible by k can be expressed as

We now return to our original problem of evaluating |A ∪ B|. To apply (13.2), we need to find |A|, |B| and |A ∩ B|. Using the result mentioned above, we see that and |B|= It remains to find |A∩B|. What does A∩B represent? Well, A ∩ B is the set of integers in S which are divisible by both 3 and 5. How to evaluate |A ∩ B|? It seems that this problem is as hard as that of evaluating |A ∪ B|.

Luckily, this is not so as there is a result in Arithmetic that can help us. Let a, b be any two positive integers. It is known that:

An integer is divisible by both a and b when and only when it is divisible by the LCM (least common multiple) of a and b.

It thus follows that A ∩ B is the set of numbers in S which are divisible by the LCM of 3 and 5. As the LCM of 3 and 5 is 15, we conclude that

Thus

Finally, by (13.2), we have

Example 13.2 Find the number of positive divisors of at least one of the numbers 5400 and 18000.

Discussion and Solution In Chapter 5, we discussed the problem of finding the number of positive divisors of a natural number by some examples. The answers obtained can be generalised to lead to the following general result:

We shall see that this result will play an important role in solving our problem.

Let x is a divisor of 5400} and x is a divisor of 18000}. Clearly, our task is to evaluate A ∪ B To apply (13.2) , we need to count |A|, |B| and |A ∩ B|.

Observe that

Thus, by applying the result stated above, we have

What does A ∩ B represent? By definition, A ∩ B is the set of common positive divisors of 5400 and 18000, and so it is the set of positive divisors of the Greatest Common Divisor (gcd) of 5400 and 18000. Since

it follows that

Hence, by (13.2), we have

Formula (13.2) provides an expression for |A ∪ B|. We shall now apply it to derive an expression for |A ∪ B ∪ C|, where A, B and C are any three finite sets.

Observe that

That is,

We shall now show an application of (13.3).

Example 13.3 Figure 13.2 shows a 4 by 8 rectangular grid with two specified corners p and q and three specified segments uv, wx and yz.

Figure 13.2

Find in the grid

 

    (i)  the number of shortest p-q routes;

   (ii)  the number of shortest p-q routes which pass through
   wx;

  (iii)  the number of shortest p-q routes which pass through at least oneof the segments uv, wx and yz;

 (iv)  the number of shortest p-q routes which do not pass through any of the segments uv, wx and yz.

Figure 13.3

Discussion and Solution (i) The problem of counting the number of shortest p-q routes in a rectangular grid was discussed in Example 5.1. Employing the idea developed there, it can be shown that the number of shortest p-q routes in the grid of Figure 13.2 is given by

(ii) As shown in Figure 13.3, a shortest p-q route passing through wx consists of a shortest p-w route (in a 2 by 3 grid), the segment wx and a shortest x-q route (in a 2 by 4 grid). Thus, the number of shortest p-q routes passing through wx is given by

(iii) The counting is more complicated in this case. We introduce three subsets of the set of shortest p-q routes below.

Let A be the set of shortest p-q routes which pass through uv, B be the set of shortest p-q routes which pass through wx, and C be the set of shortest p-q routes which pass through yz. We note that the answer we are looking for is not | A| + |B| + C| as the sets A, B, C are not pairwise disjoint. The desired answer should be |A ∪ B ∪ C|, and this gives us a chance to apply (13.3). To apply (13.3), we need to evaluate each term on the RHS of (13.3).

First, applying the idea shown in the solution of part (i), we have

Next, let us compute

Observe that A ∩ B is the set of shortest p-q routes passing through both uv and wx. Any such shortest p-q route consists of a shortest p-q route, the route uvwx and a shortest x-q route. Thus,

Likewise, we obtain

And each route in A ∩ C consists of a shortest p-u route, the segment uv, a shortest v-y route, the segment yz and a shortest z-q route, which gives

Finally, we evaluate | A ∩ B ∩ C|. Each route in A ∩ B ∩ C is a p-q route consisting of a shortest p-u route, the route uvwxyz and a shortest z-q route. Thus,

We are now in a position to evaluate |A ∪ B ∪ C|. By (13.3),

(iv) Before solving this part, recall the following identity presented in Chapter 4:

Now, let S be the set of shortest p-q routes in the grid of Figure 13.2. Then we have to evaluate |S\(A ∪ B ∪ C)|, which is equal to

By (i), we have and by (iii),

Thus, the desired answer is

In the solution of Example 13.3 (iv), we evaluated |S\(A∪B ∪C)| using (13.3) and (13.4). Now, we shall derive an explicit expression for |S\(A∪B ∪C)| and show an application of this formula.

In what follows, let S be a finite set which is “very large” in the sense that all the sets that we shall consider in a problem are subsets of S. In mathematics, we call such a set S a universal set. For instance, in Example 13.1, the universal set is {1, 2,… , 1000}; in Example 13.2, the universal set is the set of natural numbers; and in Example 13.3, the universal set is the set of shortest p-q routes in the grid of Figure 13.2.

Let A ⊆ S. We write for S\A, and call the complement of A. In the study of sets, there are two very important laws relating the set operations “union”, “intersection” and “complementation”. They are called De Morgan’s laws and are stated below.

Let A, B, C be any three subsets of S. We shall see that the set |S\(A∪B ∪C)| that we considered in Example 13.3(iv) can be expressed as Indeed,

by (13.5)

by (13.5)

It follows that Thus, by (13.3), we obtain:

We have just seen how (13.6) was derived from (13.3). It is not difficult to see also that (13.3) can be derived from (13.6). We say that these two identities are equivalent.

Now, let X = {1,2,…, m} and Y = {1,2,…, n}, where m,n ∈ . The problems of counting the number of mappings and the number of 1–1 mappings from X to Y were proposed in Problem 9.4. Let us reconsider these problems here.

Suppose that X = {1, 2, 3} and Y = {1, 2, 3, 4, 5}. How many mappings are there from X to Y? There are three elements in X, and each of them can be mapped to one of the five elements in Y. Thus the number of mappings from X to Y is given by 5 · 5 · 5 = 5³.

How many 1–1 mappings are there from X to Y? The element “1” in X can be mapped to one of the five elements in Y (5 choices). The element “2” in X can be mapped to one of the remaining four elements in Y(4 choices; excluding the image of “1”). Finally, the element “3” in X can be mapped to one of the remaining three elements in Y(3 choices; excluding the images of “1” and “2”). Thus, the number of 1-1 mappings from X to Y is given by 5 · 4 · 3.

Indeed, in general, we have:

What can be said about the number of onto mappings from X to Y? It is interesting to note that this problem is not as straightforward as those of counting the numbers of mappings and 1–1 mappings. In the following example, we shall see how Identity (13.6) is used to tackle this more difficult problem.

Example 13.4 Let X = {1, 2, 3, 4, 5} and Y = {1, 2, 3}. Find the number of onto mappings from X to Y.

Discussion and Solution Let S be the set of mappings from X to Y. We shall now introduce three subsets A, B, C of S as follows:

Let A be the set of mappings from X to Y\{1},

B be the set of mappings from X to Y\{2},

and C be the set of mappings from X to Y\{3}.

What do the sets represent? Well, is the set of mappings from X to Y which contain “1” in Y as an image, is the set of mappings from X to Y which contain “2” in Y as an image, and C is the set of mappings from X to Y which contain “3” in Y as an image. It follows that is the set of mappings from X to Y which contain “1”, “2” and “3” in Y as images; that is, is the set of onto mappings from X to Y. Thus, our task here is to evaluate ||. We can therefore apply (13.6)!

Since S is the set of mappings from {1, 2, 3, 4, 5} to {1, 2, 3}, by 13.7) , |S| = 3⁵.

Since A is the set of mappings from {1, 2, 3, 4, 5} to {2, 3}, by (13.7) again, |A| = 2⁵.

Likewise, |B| = |C| = 2⁵. As A ∩ B is the set of mappings from {1, 2, 3, 4, 5} to {3}, by (13.7) again, A ∩ B| = 1⁵ = 1.

Similarly, |A ∩ C| = |B n C| = 1.

Finally, observe that A ∩ B ∩ C is the set of mappings from X to

Now, by (13.6), we have

We have seen in this chapter how Addition Principle (13.1) can be generalised to (13.2); and, in turn, (13.2) can be extended to (13.3). Moreover, we have derived an equivalent form (13.6) of (13.3). In the next chapter, we shall introduce a more general form of (PIE) which deals with any n subsets, where n ≥ 2, and we shall see how it can be applied to solve some interesting and more complicated problems.

Exercise

13.1 Find the number of integers from the set {300, 301, … , 1000} which are multiples of 6 or 9.

13.2 How many positive integers n are there such that n is a divisor of at least one of the numbers 10³⁰ , 20²⁰?

13.3 A group of students took examinations in Chemistry, Mathematics and Physics. Among them, 12 passed Chemistry, 15 Mathematics, and 10 Physics; 8 passed both Chemistry and Mathematics, 5 both Chemistry and Physics, and 6 both Mathematics and Physics. There were 20 students who passed at least one of the three subjects. Find the number of students who passed all three subjects.

13.4 Find the number of integers from the set {1,2,---, 1000} which are

 

  (i) divisible by at least one of 2, 3 and 5;

 (ii) divisible by none of 2, 3 and 5.

 

13.5 Seven distinct objects are to be put into three distinct boxes. Find the number of ways this can be done if

 

  (i) there is no restriction;

 (ii) no box is empty.

 

13.6 The following figure shows a 5 by 8 rectangular grid with two specified corners p and q and three specified segments ab, cd and ef. Find in the grid

 

   (i) the number of shortest p-q routes;

  (ii) the number of shortest p-q routes that pass through at least one of the segments ab, cd and ef;

 (iii) the number of shortest p-q routes that do not pass through any of the segments ab, cd and ef.

13.7 Let S be the set of 3-digit numbers abc such that a,b,c ∈ {1,2,…, 9} and a, b, c are pairwise distinct. (Thus, 489 ∈ S, but 313 Find the number of members abc in S such that a ≠ 3, b ≠5 and c ≠ 7.

13.8 Find the number of integer solutions to the equation

  where 0 ≤ x ≤ 4,0 ≤ y ≤ 5 and 0 ≤ 2 ≤ 6. (See Chapter 7.)

13.9 A 5-digit ternary number is a number x₁x₂x₃x₄x₅, where x_i = 0,1 or 2 for each i = 1,2,… , 5. Thus, 00000, 01001, 21022, 11002, etc. are 5-digit ternary numbers. Find the number of 5-digit ternary numbers in which each of the “0”, “1” and “2” appears at least once.

13.10 Two scouts x₁, x₂ from School X, 3 scouts y₁, y₂, y₃ from School Y and 4 scouts z₁, z₂, z₃, z₄ from School Z get together in a meeting. In how many ways can they be arranged in a row if not all scouts from the same school are allowed to form a single block in the row? (For instance, is allowed, but and are not allowed.)