Part 1:

A couple of weeks ago, my friend John (from UK) asked me if I could explain the Inclusion-Exclusion Principle to him. Wikipedia contains an article on the same topic but John felt that it wasn’t a very helpful introduction. So, as promised, here is the post on that topic, though I managed to finish it only after some delay. (Sorry, John!)

As the title of this post suggests, the inclusion-exclusion principle can simply be described as counting all the objects outside the oval regions! We will use Venn diagrams to explain what that means.

Note: \lfloor x \rfloor denotes the greatest integer less than x.

Ok, let’s now “build” the principle step by step.

1. Suppose there are N objects out of which there are exactly N_a objects of type a. How many objects are NOT of type a? The answer is obvious: N - N_a. The Venn diagram below depicts the answer pictorially. The rounded rectangular region (with the orange border) is the set of all N objects, and the oval region (with the blue border) is the set of all N_a objects of type a. Then, the remaining white region that is outside the oval region denotes the set of all objects that are NOT of type a, and clearly, there are N - N_a of ‘em.

single-circle1.jpg

Indeed, let us take a simple example. Consider the set of first thirty natural numbers: \{ 1, 2, \ldots , 30 \}. So, N = 30. Now, out of these thirty integers, let N_2 be the number of integers divisible by 2. Then, N_2 = \lfloor 30/2 \rfloor = 15. It is easy to see that the number of integers NOT divisible by 2 equals N - N_2 = 30 - 15 = 15, which is what we would expect if we were to list all the integers not divisible by 2. Indeed, those integers are 1, 3, 5, \ldots , 29.

2. Now, suppose there are N objects out of which there are exactly N_a objects of type a and N_b objects of type b. Also, suppose there are exactly N_{ab} objects that are of both type a AND b. Then, how many objects are NOT of type a OR b? The Venn diagram below illustrates this case.

double-circles.jpg

Again, we are counting the number of objects outside the two oval regions. To answer the above question, we first need to determine the number of objects inside the two oval regions, and then subtract this number from the total, which is N. Now, one might be tempted to think that the number of objects inside the two oval regions is simply N_a + N_b. But this is only true if the two oval regions don’t intersect (i.e. they have no objects in common.) In the general case, however, the expression N_a + N_b counts N_{ab} twice! And so, we must subtract N_{ab} from the expression to get N_a + N_b - N_{ab} as the exact number of objects inside the two oval regions. We can now see that the number of objects outside the two oval regions equals N - (N_a + N_b - N_{ab}) = N - (N_a + N_b) + N_{ab}, and we are done.

Continuing with our example used earlier, let N_3 be the number of integers divisible by 3. Also, let N_6 be the number of integers divisible by 2 AND 3 (i.e. we count multiples of 6.) Now, note that N_3 = \lfloor 30/3 \rfloor = 10, and N_6 = \lfloor 30/6 \rfloor = 5.

Thus, using the formula derived above, the number of integers that are NOT divisible by 2 OR 3 equals N - (N_2 + N_3) + N_6 = 30 - (15 + 10) + 5 = 10. In fact, we can list these ten integers: 1, 5, 7, 11, 13, 17, 19, 23, 25 and 29; and this confirms our answer.

3. Now, suppose there are N objects out of which there are exactly N_a objects of type a, N_b objects of type b and N_c objects of type c. Also, let N_{ab} denote the number of objects of type a AND b, N_{bc} the number of objects of type b AND c, N_{ca} the number of objects of type c AND a, and N_{abc} the number of objects of type a, b AND c. Then, how many objects are NOT of type a, b OR c? This case is illustrated by the Venn diagram shown below.

three-circles.jpg

Once again, let us ask, what is the number of objects inside the three oval regions. A possible answer is N_a + N_b + N_c. Now this will only be true if the three oval regions are pairwise disjoint. In the general case, however, we will have to take care of overcounting, just as we did in (2) earlier. A brief thought will reveal that in the above expression, we have counted each of N_{ab}, N_{bc} and N_{ca} twice and N_{abc} thrice! To take care of this overcounting, we subtract each of N_{ab}, N_{bc} and N_{ca} once from the expression, but in doing so, we also end up subtracting N_{abc} thrice! We thus need to add N_{abc} back into the expression to get N_a + N_b + N_c - N_{ab} - N_{bc} - N_{ca} + N_{abc}, and this expression yields the exact number of objects inside the three oval regions. Therefore, the number of objects outside the three oval regions equals N - (N_a + N_b + N_c) + (N_{ab} + N_{bc} + N_{ca}) - N_{abc}. And, we are done.

Again, continuing with our earlier example, let N_5 denote the number of integers divisible by 5. Then, N_5 = \lfloor 30/5 \rfloor = 6. Also, let N_{15} denote the number of integers divisible by 3 AND 5 (i.e. we are counting multiples of 15); then, N_{15} = \lfloor 30/15 \rfloor = 2. Again, let N_{10} denote the number of integers divisible by 2 and 5; then N_{10} = \lfloor 30/10 \rfloor = 3. And, finally, let N_{30} denote the number of integers divisible by 2, 3 and 5; then N_{30} = \lfloor 30/30 \rfloor = 1.

So, the number of integers NOT divisible by 2, 3 OR 5 equals N - (N_2 + N_3 + N_5) + (N_{6} + N_{15} + N_{10}) - N_{30}

= 30 - (15 + 10 + 6) + (5 + 2 + 3) - 1 = 8. Indeed, those eight integers are 1, 7, 11, 13, 17, 19, 23 and 29.

It isn’t very hard to deduce the formula for the general case when we have a set of N objects, out of which there are N_a objects of type a, N_b objects of type b, and so on. The proof of the general formula will follow in the next post, which may include a couple of problems/solutions involving this principle.

About these ads