We use the Inclusion-Exclusion Principle to enumerate sets.

Recall the Inclusion-Exclusion Principle for two sets:

In this section, we will generalize this to sets, but first, let’s extend it from two sets to three sets.

- Proof
- Consider as one set and as the second set and apply the Inclusion-Exclusion Principle for two sets. We have: Next, use the Inclusion-Exclusion Principle for two sets on the first term, and distribute the intersection across the union in the third term to obtain: Now, use the Inclusion Exclusion Principle for two sets on the fourth term to get: Finally, the set in the last term is just , so we have the final form of the Inclusion-Exclusion Principle for three sets:

Let be the subset of consisting of the multiples of 2, be the subset of consisting of the multiples of 5, and be the subset of consisting of multiples of 9. We seek . According to the proposition, We have and . Elements in are multiples of 10, so . Elements in are multiples of 18, so . Elements in are multiples of 45, so . Lastly, elements in are multiples of 90, so . Using the Inclusion-Exclusion Principle (for three sets), we can conclude that the number of elements of that are either multiples of 2, 5 or 9 is

We now extend De Morgan’s Law to three sets.

- Proof
- Using De Morgan’s Law for two sets twice yields the result: \begin{align*} \left (A \cup B \cup C\right )^c &= \left [(A \cup B) \cup C\right ]^c \\ &= (A \cup B)^c \cap C^c \\ &= A^c \cap B^c \cap C^c \end{align*}
as desired.

The next example uses De Morgan’s Law (for three sets) in conjunction with the Rule for Complements and the Inclusion-Exclusion Principle (for three sets).

Let be the set of passwords that do not contain any digits; let be the set of passwords that do not contain any special symbols; and let be the set of passwords that do not contain any capital letters. Since our passwords must contain a digit, a special symbol and a capital letter, we seek . By De Morgan’s Law (for three sets), Then according to the Rule for Complements, where is the set of all possible passwords with no restrictions. Combining the two equations above with the Inclusion-Exclusion Principle (for three sets), we have Each of the terms on the right hand side can be computed using the Fundamental Principle of Counting. Since there are 70 different characters in total with 10 digits, 8 special symbols and 26 capital letters, In conclusion, the number of acceptable passwords is

Such permutations include MITFNSHAU and FASTHUMIN, but not IMATHUNSF, FMAISHNUT, or HTFUNISAM. Let be the set of permutations which include the word MATH; let be the set of permutations which include the word IS; and let be the set of permutations which include the word FUN. We seek . By De Morgan’s Law (for three sets), this is the same as . Let be the set of all permutations of the letters in the phrase. Then, applying the Rule for Complements, and the Inclusion-Exclusion Principle (for three sets), we have \begin{align*} |A^c \cap B^c \cap C^c| &= |(A \cup B \cup C)^c|\\ &= |S| - |A\cup B \cup C|\\ &= |S| - \Big (|A| + |B| + |C| -|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B \cap C|\Big )\\ &= |S| -|A| - |B| - |C| +|A\cap B|+|A\cap C|+|B\cap C|-|A\cap B \cap C| \end{align*}

The number of elements in is the number of permutations of the symbols MATH, I, S, F, U, N. Since this is 6 distinct symbols, . The number of elements in is the number of permutations of the symbols M, A, T, H, IS, F, U, N. Since this is 8 distinct symbols, . The number of elements in is the number of permutations of the symbols M, A, T, H, I, S, FUN. Since this is 7 distinct symbols, . The number of elements in is the number of permutations of the symbols MATH, IS, F, U, N. Since this is 5 distinct symbols, . The number of elements in is the number of permutations of the symbols MATH, I, S, FUN. Since this is 4 distinct symbols, . The number of elements in is the number of permutations of the symbols M, A, T, H, IS, FUN. Since this is 6 distinct symbols, . The number of elements in is the number of permutations of the symbols MATH, IS, FUN. Since this is 3 distinct symbols, . The number of elements in is . Hence, the total number of ways to permute the letters in the phrase MATH IS FUN which do not include any of the words MATH, IS or FUN is

Let be the permutations with 1 in the first position, be the permutations with 2 in the second position, be the permutations with 3 in the third position and be the set of all permutations. We seek . De Morgan’s Law (for three sets), the Rule for Complements and the Inclusion-Exclusion Principle (for three sets) gives: \begin{align*} |A^c \cap B^c \cap C^c| &= |(A \cup B \cup C)^c|\\ &= |S| - |A\cup B \cup C|\\ &= |S| - \Big (|A| + |B| + |C| - |A\cap B|\ - |A\cap C| - |B\cap C| + |A \cap B \cap C| \Big )\\ &= |S| - |A| - |B| - |C| + |A\cap B| + |A\cap C| + |B\cap C| - |A\cap B \cap C|\\ &= 7! - 3 \times 6! + 3 \times 5! - 4!\\ &= 3216 \end{align*}

Notice that in our computation we took advantage of the fact that certain sets had the same number of elements.

For four sets, the Inclusion-Exclusion Principle states: \begin{align*} |A \cup B \cup C \cup D | = &\;\;|A| + |B| + |C| + |D| \\ &- |A \cap B| - | (A \cap C)| - |A \cap D| - |B\cap C| - | B \cap D| - |C \cap D| \\ & +|A\cap B\cap C| + |A\cap B\cap D|+|A\cap C\cap D|+| B\cap C\cap D| \\ &- |A\cap B\cap C \cap D| \end{align*}

At this point, the number of terms is becoming quite large, so summation notation is to be preferred:

With no restrictions on the variables (except that they be non-negative integers), the total number of solutions is by the stars and bars method. Let be the set of all solutions which have for . We wish to find . De Morgan’s Law (for four sets) and the Rule for Complements \begin{align*} |A_1^c \cap A_2^c \cap A_3^c \cap A_4^c| &= |(A_1 \cup A_2 \cup A_3 \cup A_4)^c|\\ &= |S| - |A_1 \cup A_2 \cup A_3 \cup A_4| \end{align*}

Now, the Inclusion-Exclusion Principle (for four sets) gives: Since the conditions on the four variables is the same (), the number of elements in each intersection of a particular number of sets will be equal. Thus, ; for the six intersections of this form; for the four intersections of this form; and . Hence,

We are now ready to state and prove the general case of the Inclusion-Exclusion Principle.

- Proof
- We will prove the proposition by induction on the number of sets, . The
base case, was proved in section 2.1. For the induction hypothesis, we assume that
the result is true for some number of sets . We then wish to show that the result is
true for sets. We will do this in a manner similar to the way we began
this section, obtaining the Inclusion-Exclusion Principle for three sets as
a consequence of the result for two sets. Thus, we consider the union of
the first sets to be a single set and we obtain: In the last term, we can
distribute the intersection over the unions to obtain a union of sets: We can
apply the induction hypothesis the number of elements in this union, and
noting that , we obtain Inserting this back into the first equation, and
applying the induction hypothesis to the first term in that equation, we get \begin{align*} |A_1 \cup A_2 &\cup \cdots \cup A_n \cup A_{n+1}| \\[6 pt] & =|A_1 \cup A_2 \cup \cdots \cup A_n| + |A_{n+1}| - |(A_1 \cup A_2 \cup \cdots \cup A_n) \cap A_{n+1}| \\[7 pt] &= \bigg ( \sum _{i =1}^n |A_i| - \sum _{1 =i<j}^n |A_i\cap A_j| \\ &\quad +\sum _{1 =i<j< k}^n |A_i\cap A_j \cap A_k| - \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n|\bigg ) \\ &\quad + |A_{n+1}| - \bigg (\sum _{i = 1}^n |A_i \cap A_{n+1}| - \sum _{1 = i < j}^n |A_i \cap A_j \cap A_{n+1}| \\ &\;\;+ \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_{n+1}|\bigg )\\ &= \sum _{i =1}^{n+1} |A_i| - \sum _{1 =i<j}^{n+1} |A_i\cap A_j| \\ & \quad +\sum _{1 =i<j< k}^{n+1} |A_i\cap A_j \cap A_k| - \cdots + (-1)^{n} |A_1 \cap A_2 \cap \cdots \cap A_{n+1}| \\ \end{align*}
as required.

We now present a second proof, using a counting argument used in the proof of the two set case.

- Proof
- (combinatorial proof)

Let and suppose that is an element of of the sets, . We need to show that the proposed formula accounts for exactly once. We will analyze the accounting for term by term. The first term of the Inclusion-Exclusion Principle is and this term accounts for exactly times, since is an element of of the sets in the sum. Note that is also . The second term of the Inclusion-Exclusion Principle is and this term accounts for exactly times since for to be in , both of these sets must be among the sets that contain . Similarly, the third term of the Inclusion-Exclusion Principle is and this term accounts for exactly times. Lastly, the term of the Inclusion-Exclusion Principle involves the intersections of of the sets. In this term, is accounted for times. The remaining terms of the Inclusion-Exclusion formula contain more than intersections and hence they will not account for at all (or zero times). In total, the number of times is accounted for by the Inclusion-Exclusion formula is From the binomial theorem with and and replacing and with and respectively, we have Thus the Inclusion-Exclusion formula accounts for in way, as desired.