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:
(problem 1) How many numbers from the given set are multiples of the given numbers and ?
a)
b)
c)

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).

(problem 2) Computer passwords are eight characters long where a character can be either an upper case letter, lower case letter, digit 0-9, or one of 8 special symbols. How many passwords are possible if a password must contain at least one digit, at least one lower case letter and at least one upper case letter?
(problem 3) How many permutations are there of the letters in the phrase YOU HAD TIME in which do not include any of the words YOU, HAD or TIME?
(problem 4) How many permutations are there of the letters in the word ABCDEF in which the letter A is not first, the letter C is not third and the letter F is not last?

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:

(problem 5a) How many non-negative integer solutions are there to the equation if for
(problem 5b) How many permutations are there of the numbers 1-7 such that 1 is not in the first position, 2 is not in the second position, 3 is not in the third position and 4 is not in the fourth position?
and are the same for all

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.
2024-09-27 14:04:48