The inclusion/exclusion principle: counting unions

In this unit, we’re going to learn how to count the elements of a union of sets. Let us consider an example. In a class, students like either maths or history. And 20 of them like maths, and 15 like history. 10 of the students love both maths and history. How many are the students? Well, recall that the number of elements of a union is the sum of the elements of the 2 sets minus the number of elements of the intersection. So let us apply this formula. And we get 20 plus 15 minus the number of students that love both maths and history. So we get 25. But how to manage if we have more sets than 2?

Let us consider 3 sets, X, Y, and Z, finite sets.

Then, well, it turns out that the number of elements of the union of X with Y with Z equals the sum of the elements of the sets minus the number of elements of the 2 by 2 intersections plus the number of elements of intersection of the 3 sets. Let us give a look on how the proof works.

Well, let us introduce the term S, which is the right- hand side term of the above equality. That is the sum of the elements of X, Y, and Z minus the sum of the elements of the intersection that are taken 2 by 2 of these sets plus the number of elements of the intersection of the 3 sets.

The proof goes as follows. We consider an element X of the union of X with Y with Z, and we look how many times small x is counted in the sum S of big X, Y, and Z. We consider different cases. x may belong to just 1 of the sets or to just 2 of the sets or to all the 3 sets. Let’s see how it works. Let us consider, for instance, the case where x belongs to one of the 3 sets, just one of the 3 sets, say, X. Well, then we count 1 as an element of X.

And we count 0 as element of Y, Z, 0 as elements of X intersection with Y, Y intersection with Z, X intersection with Z, and also for X intersection with Y and with Z. So when we count, taking the sign’s minus in front of the 2 by 2 intersections, we get 1. So it is counted 1 time in the sum. Assume now that a x belongs to just 2 sets, say, X and Y. Well, we count 1 for X, 1 for Y, 0 for Z. Then we count minus 1 for the intersection of X with Y, 0 for the other intersections. So the sum gives 1 plus 1 minus 1, 1.

And finally, let us consider the case where x belongs to all of the 3 sets. Well, here we count 1 for the 3 sets X, Y, and Z, minus 1 for the intersection 2 by 2, plus 1 for the intersection of X with Y with Z. When we count, we find 3 minus 3 plus 1. And we get 1. So in any case, the elements are counted just once, and this proves the equality. We are going now to generalise the Inclusion-Exclusion Principle to an arbitrary number n of sets. Let us consider n sets, A1,…, An. It is convenient to introduce a notation. By Sigma 1, we denote the sum of the elements of these sets.

By Sigma 2, we denote the sum of the elements of the pairwise intersection of these sets. And for every k between 1 and n, we denote by Sigma k the sum of the number of elements of the intersections of k of these sets, all possible intersections whose number is, of course, the number of subsets of k elements among n. That is the binomial n over k.

Finally, Sigma n, well, there is just intersection of the n sets. That is the cardinality of the intersection of A1 with A2 with…with An. Let us now formulate the inclusion-exclusion principle for n sets. Well, take n sets A1, …, An, the inclusion exclusion principle states that the cardinality of the union of these sets equals the sum with alternate signs of Sigma one, Sigma two, Sigma three and so on. More precisely, Sigma one, minus Sigma two, plus Sigma three, and so on, up to Sigma n with the sign minus if n is even, plus if n is odd.