Skip main navigation

The inclusion/exclusion principle: counting unions

The inclusion/exclusion principle: counting unions
9.8
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?
66.3
Let us consider 3 sets, X, Y, and Z, finite sets.
73.3
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.
102.1
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.
127.7
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.
170.6
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.
224.5
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.
275.6
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.
306.4
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.

How to count the number of elements of a finite union of sets? This is quite easy when you deal with two sets: just count the number of elements of each of the sets and subtract the number of elements of their intersection (that was counted twice). How about with 3 sets, or even more? Carlo will explain it in the next video.

You can access the content of the video in the PDF file at the bottom of this step.

This article is from the free online

Combinatorics: Strategies and Methods for Counting

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education