The Inclusion-Exclusion Principle

The inclusion-exclusion principle

The inclusion-exclusion principle is a counting technique used to count the number of elements in a union of sets so that each element is counted only once.

Case of two sets

Remember that the relation between the cardinalities of two arbitrary sets, $A$ and $B$, and the cardinality of their union is as follows:

If $A$ and $B$ are disjoint sets, then there are no common elements, and we have the following relation of cardinalities:

In general, $A$ and $B$ may or may not be disjoint. So, we use the inclusion-exclusion principle to find out the cardinality of $A\cup B$, which states the following relation:

Let’s look at the reason behind why this equation holds. Here, $\lvert A \rvert$ is the number of elements in the set, including those common to $B$. Likewise, $\lvert B \rvert$ is the number of elements in $B$, including those that are common to $A$. Therefore, the common elements of $A$ and $B$ are counted twice, and we must subtract the number of such elements represented by $\lvert A \cap B \rvert$. This explains the equation of the inclusion-exclusion principle, which is further illustrated in the following figure:

Example 1

In a class, 30 students are enrolled in physics, and 25 students are enrolled in mathematics. If 15 students are enrolled in both physics and mathematics, what is the total number of students in that class? Let’s assume that there is no student in the class who is not enrolled in either of these subjects.

To solve this problem, let the set of students in the class be $C$. Moreover, we represent the set of students enrolled in physics with $P$ and the set of students enrolled in mathematics with $M$. Using the ...