Principle of Inclusion-Exclusion

Section 3.2 Principle of Inclusion-Exclusion

Objectives

State the Principle of Inclusion-Exclusion and apply it to problems to compute set cardinalities (for combinations of two to four sets).
Sketch Venn Diagrams that correspond to a given scenario or problem.

Video: Principle of Inclusion-Exclusion

We first recall that in order to count the number of elements of a set \(U\) that don't satisfy a given condition, one can first count the number of elements that do, and then subtract from the cardinality of \(U\text{.}\)

Example 3.2.1. Not Divisible by 3.

How many integers in \(U = \{1,2,\ldots,25\}\) are not divisible by 3?

Solution We first count the number of integers in the set that are divisible by 3: there are

\begin{equation*} \left\lfloor \frac{25}{3}\right\rfloor = 8 \end{equation*}

of them.

Note that the notation \(\lfloor n \rfloor\) denotes the floor function, which returns the largest integer that is less than or equal to \(n\text{.}\)

Subtracting, we get \(25 - 8 = 17\) integers in the set \(U\) that are not divisible by 3. (Check that this is the correct number!)

Note that this solution can be expressed in terms of sets: if \(U = \{1,2,\ldots,25\}\) is the universe, and \(A\) is the set of integers in \(U\) divisible by 3, then the desired quantity is \(|A^c|\text{,}\) and

\begin{equation*} |A^c| = |U| - |A|\text{.} \end{equation*}

What if we added a second condition to avoid?

Example 3.2.2. Not Divisible by 3 or 4.

How many numbers in \(U = \{1,2,\ldots,25\}\) are not divisible by 3 or 4?

Solution

Following the previous example, there are \(8\) integers in \(U\) that are divisible by 3. Also, there are \(\lfloor \frac{25}{4} \rfloor = 6\) integers in \(U\) divisible by 4.

However, after subtracting \(25 - 8 - 6 = 11\text{,}\) we've actually removed some numbers twice: those numbers that are divisible by both 3 and 4 (i.e. divisible by 12). This means we need to ‘add them back in’ again.

There are \(\lfloor \frac{25}{12} \rfloor = 2\) of these numbers, so the correct total is

\begin{equation*} 25 - 8 - 6 + 2 = 13 \end{equation*}

integers in the set that are neither divisible by 3 nor by 4.

We can again write the solution to Example 3.2.2 in terms of sets:

\(\displaystyle U = \{1,2,\ldots,25\}\)
\(A_1 = \) integers in \(U\) divisible by 3 \(= \{3,6,9,12,15,18,21,24\}\)
\(A_2 = \) integers in \(U\) divisible by 4 \(= \{4,8,12,16,20,24\}\)
\(A_1 \cup A_2 = \) integers in \(U\) divisible by either 3 or 4 \(= \{3,4,6,8,9,12,15,16,18,20,21,24\}\)
Desired set: \((A_1 \cup A_2)^c = \) integers in \(U\) divisible by neither 3 nor 4.

Observe that when we subtract \(|A_1|\) and \(|A_2|\) from \(|U|\text{,}\) we are subtracting the elements in the intersection \(A_1 \cap A_2 = \{12, 24\}\) two times. So to determine the quantity \(|(A_1 \cup A_2)^c|\) we computed:

\begin{equation*} |(A_1 \cup A_2)^c| = |U| - |A_1| - |A_2| + |A_1 \cap A_2|\text{.} \end{equation*}

Remark 3.2.3.

Do not confuse the operations \(|A| - |B|\) and \(A \setminus B\text{.}\) The first is a difference of two numbers, while the second is a set operation that also results in a set. In fact, it is not the case that \(|A| - |B| = |A \setminus B|\) in general. (Can you come up with a counterexample?)

Checkpoint 3.2.4. Not Divisible by 7 or 11.

How many integers in \(\{1,2,3,\ldots,2020\}\) are not divisible by 7 or 11?

Answer

\(1575\text{.}\)

Now suppose we add a third condition to avoid, that is, a third set \(A_3\) to remove. Consider the problem of determining the number of elements in the set \((A_1 \cup A_2 \cup A_3)^c\text{.}\)

Venn diagram illustrating the complement of the union of three sets.

The idea now is to replicate the 2-set scenario by first subtracting \(|A_1| + |A_2| + |A_3|\) from \(|U|\text{,}\) then to add back what was removed more than once. This means we have to add back \(|A_1 \cap A_2|\text{,}\) \(|A_1 \cap A_3|\text{,}\) and \(|A_2 \cap A_3|\text{.}\)

However, elements in the intersection of all three sets \(A_1 \cap A_2 \cap A_3\) have been removed three times and added back three times at this point. This means we should subtract

\begin{equation*} |A_1 \cap A_2 \cap A_3| \end{equation*}

one more time so that we remove all the elements we need to remove.

To summarize: (note the alternating signs)

\begin{align*} |(A_1 \cup A_2 \cup A_3)^c| = |U| \amp \underbrace{- |A_1| - |A_2| - |A_3|}_{\text{single sets}} \\ \amp \underbrace{+ |A_1 \cap A_2| + |A_1 \cap A_3| + |A_2 \cap A_3|}_{\text{intersections of pairs}}\\ \amp \underbrace{- |A_1 \cap A_2 \cap A_3|}_{\text{intersection of all three}}\text{.} \end{align*}

Checkpoint 3.2.5. Not Divisible by 3, 7, or 11.

How many integers in \(\{1,2,\ldots,2020\}\) are not divisible by 3, 7, or 11?

Answer

\(1051\text{.}\)

Now we can state the Principle of Inclusion-Exclusion (or PIE) in full generality. There are a number of ways to prove this, but the usual method is to show that each item belonging to none of the \(A_i\)'s contribute 1 to the total; while all other items contribute 0 to the total.

Theorem 3.2.6. Principle of Inclusion-Exclusion.

Given a universe \(U\) of items and subsets \(A_1,A_2,\ldots,A_n\) of the items, the number \(N\) of items belonging to none of these subsets is given by

\begin{align*} N \amp = \sum_{S \subseteq \{1,2,\ldots,n\}} (-1)^{|S|} \left| \bigcap_{i\in S} A_i\right|\\ \amp = |U| - \sum_{i = 1}^n |A_i| + \sum_{1 \leq i \lt j \leq n} |A_i \cap A_j| - \sum_{1 \leq i \lt j \lt k \leq n} |A_i \cap A_j \cap A_k| + \cdots \end{align*}

Proof.

Suppose that the element \(x\) is in none of the \(A_i\)'s. Then it is counted exactly once in the sum, in the first term \(|U|\text{.}\)

Now suppose that the element \(y\) is in some collection of \(A_i\)'s. Let \(T = \{i : y \in A_i\}\) be the set of indices of sets that contain \(y\text{.}\) (For example, if \(y\) is in \(A_1\text{,}\) \(A_3\text{,}\) and \(A_4\text{,}\) then \(T = \{1,3,4\}\text{.}\)) Then for each subset \(S\) of \(T\text{,}\) there is a corresponding term in the formula above.

Note that the formula contributes a \(+1\) for intersections of even numbers of sets (or for \(|S|\) even); and a \(-1\) for intersections of odd numbers of sets (for \(|S|\) odd). Hence the total contribution for the element \(y\) is

\begin{equation*} \sum_{S \subseteq T} (-1)^{|S|} = \sum_{k=0}^{|T|} (-1)^k\binom{|T|}{k}\text{.} \end{equation*}

Applying Theorem 2.3.5, we see that this is equal to

\begin{equation*} \sum_{k=0}^{|T|} (-1)^k\binom{|T|}{k} = \sum_{k=0}^{|T|} (1)^{|T|-k}(-1)^k\binom{|T|}{k} = \left( 1 + (-1) \right)^{|T|} = 0\text{,} \end{equation*}

which is what we needed to prove.

Checkpoint 3.2.7. PIE for Four Sets.

Given a universe \(U\) and four sets \(A_1, A_2, A_3, A_4\) in \(U\text{,}\) write out the complete formula for \(|(A_1 \cup A_2 \cup A_3 \cup A_4)^c|\text{.}\)

Example 3.2.8. Word Rearragements.

Count the number of arrangements of the letters in the word

EQUATION

such that

vowels are not in alphabetical order when read left-to-right; and
consontants are not in alphabetical order when read left-to-right.

Solution

Let \(A_1\) be the set of arrangements where vowels are in alphabetical order, and \(A_2\) the set of arrangements where consonants are in alphabetical order. Then the desired number is \(|(A_1 \cup A_2)^c| = |U| - |A_1| - |A_2| + |A_1 \cap A_2|\text{,}\) by Theorem 3.2.6.

We compute each quantity:

\(|U| = 8!\text{,}\) the number of permutations of the letters.
\(|A_1| = 3! \cdot \binom{8}{3}\) (permute the consonants first, then insert among vowels using the Balls in Bins Formula)
\(|A_2| = 5! \cdot \binom{8}{5}\) (permute the vowels first, then insert among consontants)
\(|A_1 \cap A_2| = \binom{8}{5}\) (vowels and consonants are in a fixed order; just pick 5 slots for vowels to be in and the rest follows)

Hence \(|(A_1 \cup A_2)^c| = |U| - |A_1| - |A_2| + |A_1 \cap A_2| = 8! - 3!\binom{8}{3} - 5!\binom{8}{5} + \binom{8}{5}\text{,}\) or 33320.

Checkpoint 3.2.9. Relatively Prime Numbers.

Use Theorem 3.2.6 to determine how many natural numbers less than 120 are relatively prime with 120.

Hint

Consider prime factors of 120.

Exploration 3.2.1. Euler's Totient Function.

Given \(n \in \mathbb{N}\) and \(\{p_1,p_2,\ldots,p_k\}\) its set of prime factors, we will prove the following formula for the number of natural numbers less than \(n\) (denoted by \(\phi(n)\)) that are also relatively prime with \(n\text{:}\)

\begin{equation*} \phi(n) = \sum_{S \subseteq \{1,2,\ldots,k\}}(-1)^{|S|}\dfrac{n}{\prod_{i\in S} p_i}\text{.} \end{equation*}

(This is known as Euler's totient function.)

(a)

Define \(A_i\) to be the set of natural numbers less than \(n\) that are divisible by \(p_i\text{.}\) Compute the value of \(|A_i|\text{.}\)

Hint

Example 3.2.1.

(b)

For any set \(S \subseteq \{1,2,\ldots,k\}\text{,}\) compute the value of \(\left|\displaystyle\bigcap_{i\in S} A_i \right|\text{.}\)

(c)

Express \(\phi(n)\) as a combination of the sets \(A_i\) and apply Theorem 3.2.6 to obtain the desired formula.

Checkpoint 3.2.10. Compute \(\phi(100)\) and \(\phi(135)\).

Use the formula in Exploration 3.2.1 to compute \(\phi(100)\) and \(\phi(135)\text{.}\)

Checkpoint 3.2.11. One Card of Each Suit.

Use Theorem 3.2.6 to determine how many five-card hands can be drawn from a standard deck of cards such that there is at least one card of each suit.

Checkpoint 3.2.12. Nonnegative Integer Solutions.

Use Theorem 3.2.6 to determine how many nonnegative integer solutions there are to \(x_1 + x_2 + x_3 = 10\text{,}\) \(x_1 \leq 3\text{,}\) \(x_2 \leq 4\text{,}\) \(x_3 \leq 8\text{.}\)

Hint

Define \(A_1\) to be the set of solutions such that \(x_1 \gt 3\text{,}\) etc.

Solutions Solutions to Selected Checkpoints

Checkpoint 3.2.11. One Card of Each Suit.

Solution

Checkpoint 3.2.12. Nonnegative Integer Solutions.

Solution