Lecture 32 — Inclusion/Exclusion
Counting a union of sets that are not disjoint. The addition rule only adds sizes when no element is in two of the sets; when they overlap, adding the sizes counts the shared elements more than once, and inclusion/exclusion subtracts the overlaps back out. The rule for two and three sets, why it counts every element exactly once, a proof of the three-set rule from the two-set one, and the general rule for \(n\) sets, then five counting questions, the last of them a probability. Pre-work: Video 041 (Inclusion/Exclusion). The principle, the complement for “none of them”, counting multiples with the floor function and the probability form are collected in inclusion-exclusion. The addition and difference rules it extends are in counting-principles.
Goals
- Understand the inclusion/exclusion principle for two and three sets.
- Know how to use the inclusion/exclusion principle to solve counting problems.
Two questions to keep in mind:
- In the three-set rule, why is \(|A \cap B \cap C|\) added back once and not twice? The region counts show it.
- Could the two-set rule be applied twice instead of learning a three-set rule? Yes, and doing it proves the three-set rule.
Two sets
Inclusion/exclusion for two sets. For finite sets \(A\) and \(B\), \[|A \cup B| = |A| + |B| - |A \cap B|.\]
\(|A|\) counts every element of \(A\), including those also in \(B\). \(|B|\) counts every element of \(B\), including those also in \(A\). So \(|A| + |B|\) counts each element of \(A \cap B\) twice and everything else in \(A \cup B\) once. Subtracting \(|A \cap B|\) takes one of the two counts away.
When \(A\) and \(B\) are disjoint, \(|A \cap B| = 0\) and this is the addition rule (counting-principles). Inclusion/exclusion is what the addition rule becomes when the sets are allowed to overlap.
Figure 1: How many times each region of \(A \cup B\) is counted. Adding \(|A|\) and \(|B|\) counts the two outer regions once each but the overlap twice, once inside \(A\) and once inside \(B\). Subtracting \(|A \cap B|\) removes one count from the overlap only, so every element of \(A \cup B\) ends up counted exactly once.
Three sets
Inclusion/exclusion for three sets. For finite sets \(A\), \(B\) and \(C\), \[|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.\]
Three circles cut the plane into seven regions inside the union, and the formula is right exactly when each of the seven ends up counted once. Track the counts term by term.
- Add the single sets. \(|A| + |B| + |C|\) counts an element once for each set it is in. Regions in one set are counted once, regions in exactly two sets twice, and the centre, \(A \cap B \cap C\), three times.
- Subtract the pairs. An element in exactly two sets, say \(A\) and \(B\) but not \(C\), is in only one of the three pairwise intersections, \(A \cap B\), so it loses one count and drops from 2 to 1. An element of the centre is in all three pairwise intersections, so it loses three counts and drops from 3 to 0.
- Add the triple. Only the centre is in \(A \cap B \cap C\). Adding \(|A \cap B \cap C|\) once brings it from 0 to 1 and leaves every other region alone.
So the triple intersection is added back once because once is exactly what the centre is short after the pairs are subtracted. Adding it twice would leave the centre counted twice.
Figure 2: The number of times each of the seven regions is counted after each stage of the three-set formula. The three single-set sizes count a region once for each circle it lies in, so the centre is counted three times. Subtracting the three pairwise intersections removes one count from each two-set region but three from the centre, which drops to 0. Adding the triple intersection once restores the centre, and every region is counted exactly once.
Worked: the three-set rule from the two-set rule
Could the inclusion/exclusion rule for two sets be used twice instead of a separate rule for three sets?
Yes. Treat \(B \cup C\) as a single set, apply the two-set rule to \(A\) and \(B \cup C\), and the three-set rule falls out. The laws are cited by their numbers in the table of set identities on the formula-sheet. The two-set rule is used with different sets in the role of \(X\) and \(Y\) in
\[|X \cup Y| = |X| + |Y| - |X \cap Y|.\]
\[\begin{aligned} |A \cup B \cup C| &= |A \cup (B \cup C)| && \text{by the associative law (2a)} \\ &= |A| + |B \cup C| - |A \cap (B \cup C)| && \text{two-set rule, } X = A,\ Y = B \cup C \\ &= |A| + |B| + |C| - |B \cap C| - |A \cap (B \cup C)| && \text{two-set rule, } X = B,\ Y = C \\ &= |A| + |B| + |C| - |B \cap C| - |(A \cap B) \cup (A \cap C)| && \text{by the distributive law (3b)} \\ &= |A| + |B| + |C| - |B \cap C| - \big(|A \cap B| + |A \cap C| - |(A \cap B) \cap (A \cap C)|\big) && \text{two-set rule, } X = A \cap B,\ Y = A \cap C \\ &= |A| + |B| + |C| - |B \cap C| - \big(|A \cap B| + |A \cap C| - |A \cap B \cap C|\big) && \text{see below} \\ &= |A| + |B| + |C| - |B \cap C| - |A \cap B| - |A \cap C| + |A \cap B \cap C| && \text{expanding the bracket} \\ &= |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| && \text{rearranging.} \end{aligned}\]
The step marked “see below” simplifies \((A \cap B) \cap (A \cap C)\). Regroup with the commutative and associative laws (1b, 2b) to get \((A \cap A) \cap (B \cap C)\), and \(A \cap A = A\) by the idempotent law (7b), leaving \(A \cap B \cap C\).
The sign of the triple term comes from the bracket. The rule for \(A \cap B\) and \(A \cap C\) subtracts their overlap, and that whole bracket is itself subtracted, so the overlap ends up added. This is the same “once, not twice” seen in the region counts, reached by algebra.
Figure 3: The three-set rule as three uses of the two-set rule. First \(A\) is separated from \(B \cup C\). That leaves two unions to count: \(B \cup C\), and the part of \(A\) inside \(B \cup C\), which the distributive law writes as \((A \cap B) \cup (A \cap C)\). Each of those is a union of two sets and gets the two-set rule. The overlap of \(A \cap B\) and \(A \cap C\) is \(A \cap B \cap C\), and because it sits inside a bracket that is subtracted, it ends up added.
Worked: divisible by neither 7 nor 11
Among the integers \(1, 2, \dots, 77\), seven are divisible by 11, eleven are divisible by 7, and one is divisible by both 7 and 11. How many of the integers \(1, 2, \dots, 77\) are divisible by neither 7 nor 11?
Let \(A\) be the set of integers from \(1, 2, \dots, 77\) that are divisible by 11, and \(B\) the set of those divisible by 7. Then
\[A = \{11, 22, 33, 44, 55, 66, 77\}, \qquad B = \{7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77\},\]
so \(|A| = 7\), \(|B| = 11\), and \(A \cap B = \{77\}\), since \(77 = 7 \cdot 11\) is the only multiple of both that is at most 77.
\(A \cup B\) is the set of integers from \(1, \dots, 77\) divisible by at least one of 7 and 11. By inclusion/exclusion,
\[|A \cup B| = |A| + |B| - |A \cap B| = 7 + 11 - 1 = 17.\]
The integers divisible by neither are the ones outside \(A \cup B\), so there are
\[77 - |A \cup B| = 77 - 17 = 60.\]
Adding \(7 + 11 = 18\) would count 77 twice, once as a multiple of 11 and once as a multiple of 7, and give 59. Checking every integer from 1 to 77 directly also gives 60.
Figure 4: The integers from 1 to 77, with the multiples of 11 in \(A\) and the multiples of 7 in \(B\). The only integer in both is \(77 = 7 \cdot 11\), so the union has \(7 + 11 - 1 = 17\) elements. The 60 integers outside both circles are the ones divisible by neither 7 nor 11.
The general rule
The pattern continues for any number of finite sets: add the sizes of the single sets, subtract the sizes of the pairwise intersections, add the sizes of the triple intersections, subtract the four-way intersections, and so on, alternating, until the intersection of all \(n\) sets.
\[\begin{aligned} |A_1 \cup A_2| &= |A_1| + |A_2| - |A_1 \cap A_2| \\ |A_1 \cup A_2 \cup A_3| &= |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3| \end{aligned}\]
Adding a fourth set \(A_4\) brings one more term into each group and a new last group: \(+|A_4|\) with the singles; \(-|A_1 \cap A_4| - |A_2 \cap A_4| - |A_3 \cap A_4|\) with the pairs; \(+|A_1 \cap A_2 \cap A_4| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4|\) with the triples; and the four-way term \(-|A_1 \cap A_2 \cap A_3 \cap A_4|\). Four singles, six pairs, four triples and one four-way intersection, 15 terms in all.
Inclusion/exclusion for \(n\) sets. For finite sets \(A_1, A_2, \dots, A_n\), \[|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{1 \leq i \leq n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|.\]
The conditions \(i < j\) and \(i < j < k\) make each pair and each triple appear once: \(A_1 \cap A_2\) is in the second sum, and \(A_2 \cap A_1\), the same set, is not counted again.
The same rule can be written as one sum over the sets of indices. For a set \(S\) of indices, \(\bigcap_{t \in S} A_t\) is the intersection of the sets whose index is in \(S\); with \(S = \{2, 3, 6\}\) it is \(A_2 \cap A_3 \cap A_6\). Then
\[|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{\substack{S \subseteq \{1, 2, \dots, n\} \\ S \neq \emptyset}} (-1)^{|S|+1} \left| \bigcap_{t \in S} A_t \right|.\]
The sign \((-1)^{|S|+1}\) is \(+\) when \(S\) has an odd number of indices and \(-\) when it has an even number, which is the alternation above. \(S\) has to be non-empty: an intersection of no sets at all is not one of the terms. Why every element of the union is counted exactly once, for any \(n\), is in inclusion-exclusion.
Figure 5: The fifteen terms of inclusion/exclusion for four sets, one for each non-empty set \(S\) of indices, in rows by the size of \(S\) with the sign each row carries. A line joins \(S\) to each index set with one more index. An element \(x\) lying in \(A_1\), \(A_2\) and \(A_3\) but not in \(A_4\) is counted by a term exactly when every set in that term contains \(x\), that is, when \(S \subseteq {1, 2, 3}\); those are the highlighted terms. Three of them are added, three subtracted and one added, so \(x\) is counted \(3 - 3 + 1 = 1\) time. Any \(S\) containing 4 misses \(x\) altogether.
Worked: words containing “a” and “b”
In a list of 100 words, there are 47 that contain an “a” and 18 that contain a “b”. If there are 51 that contain neither an “a” nor a “b”, then how many contain both an “a” and a “b”?
Let \(A\) be the set of words that contain an “a” and \(B\) the set of words that contain a “b”. The question wants \(|A \cap B|\).
This runs inclusion/exclusion backwards: the union is found first and the intersection is the unknown. The words containing an “a” or a “b” are all the words except the 51 that contain neither, so
\[|A \cup B| = 100 - |(A \cup B)^c| = 100 - 51 = 49.\]
Rearranging \(|A \cup B| = |A| + |B| - |A \cap B|\),
\[|A \cap B| = |A| + |B| - |A \cup B| = 47 + 18 - 49 = 16.\]
So 16 words contain both. Check by filling in the four regions: \(47 - 16 = 31\) contain an “a” but no “b”, \(18 - 16 = 2\) contain a “b” but no “a”, 16 contain both and 51 neither, and \(31 + 16 + 2 + 51 = 100\).
Figure 6: The 100 words split into the four regions of a two-set Venn diagram. The 51 outside both circles fix the union at \(100 - 51 = 49\). The two circles hold \(47 + 18 = 65\) counts between them, 16 more than the 49 words they contain, and those 16 extra counts are the words in both. The circles are not drawn to scale.
Worked: attendance and exam marks
In 2015, there were 411 students enrolled in MATH1061. Of these, 270 did not come to class regularly and 118 scored at least 60% on the final exam. If 31 came to class regularly and got less than 60% on the final exam, then how many did not come to class regularly and scored at least 60% on the final exam?
Let \(A\) be the set of students who did not come to class regularly, and \(B\) the set of students who scored at least 60% on the final exam. The question wants \(|A \cap B|\).
The 31 students who came regularly and scored below 60% are in neither \(A\) nor \(B\): coming regularly puts them outside \(A\), and scoring below 60% puts them outside \(B\). So \(|(A \cup B)^c| = 31\) and \(|A \cup B| = 411 - 31 = 380\). Then
\[\begin{aligned} |A \cap B| &= |A| + |B| - |A \cup B| \\ &= |A| + |B| - \big(411 - |(A \cup B)^c|\big) \\ &= 270 + 118 - (411 - 31) \\ &= 388 - 380 = 8. \end{aligned}\]
So 8 students did not come to class regularly and still scored at least 60%. The four regions are \(270 - 8 = 262\) in \(A\) only, 8 in both, \(118 - 8 = 110\) in \(B\) only and 31 in neither, which add to \(411\).
The step to be careful with is reading “came regularly and got less than 60%” as the complement of the union. It is the negation of both conditions, \(A^c \cap B^c\), which by De Morgan’s law (9a) is \((A \cup B)^c\).
Figure 7: The 411 students by attendance and exam result. \(A\) is the students who did not come to class regularly and \(B\) those who scored at least 60%. The 31 who came regularly and scored below 60% are outside both circles, so the union holds 380, and the overlap is the \(270 + 118 - 380 = 8\) students counted in both circles. The circles are not drawn to scale.
Worked: divisible by none of 3, 5, 7
How many of the integers \(\{1, 2, \dots, 105\}\) are divisible by none of 3, 5 or 7?
Let \(S = \{1, 2, \dots, 105\}\). Let \(A\) be the set of integers in \(S\) divisible by 3, \(B\) those divisible by 5, and \(C\) those divisible by 7.
Single sets. Every third integer is a multiple of 3, so \(|A|\) is \(105 \div 3\). Since \(105 = 3 \cdot 5 \cdot 7\), each division is exact.
\[|A| = \frac{105}{3} = 35, \qquad |B| = \frac{105}{5} = 21, \qquad |C| = \frac{105}{7} = 15.\]
Pairs. An integer divisible by both 3 and 5 is divisible by 15, because 3 and 5 are different primes, so \(A \cap B = \{x \in S : 15 \mid x\}\). The same holds for every pair and for all three.
\[|A \cap B| = \frac{105}{15} = 7, \qquad |A \cap C| = \frac{105}{21} = 5, \qquad |B \cap C| = \frac{105}{35} = 3, \qquad |A \cap B \cap C| = \frac{105}{105} = 1.\]
The union. By inclusion/exclusion for three sets,
\[\begin{aligned} |A \cup B \cup C| &= |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \\ &= 35 + 21 + 15 - 7 - 5 - 3 + 1 \\ &= 71 - 15 + 1 = 57. \end{aligned}\]
None of them. The integers divisible by none of 3, 5 and 7 are the ones outside the union:
\[|(A \cup B \cup C)^c| = |S| - |A \cup B \cup C| = 105 - 57 = 48.\]
So 48 of the integers are divisible by none of 3, 5 or 7. Checking all 105 directly gives the same.
Figure 8: The integers from 1 to 105, sorted by which of 3, 5 and 7 divide them. Only 105 is in all three sets. The two-set regions hold the multiples of 15, 21 and 35 other than 105, and the single-set regions what is left of each set. The seven regions inside add to 57, so 48 integers lie outside every circle.
Worked: 1 and 2 first or 5 last
What is the probability that a randomly chosen permutation of \(\{1, 2, 3, 4, 5\}\) has 1 and 2 in the first two positions (not necessarily in that order), or has 5 in the last position?
With every permutation equally likely, the probability of an event is the number of permutations in it divided by the number of permutations, \(5! = 120\) (probability). Let \(A\) be the set of permutations with 1 and 2 in the first two positions, and \(B\) the set of permutations with 5 in the last position. The event is \(A \cup B\).
- \(|A|\). The first two positions hold 1 and 2 in one of \(2\) orders, 12 or 21. The other three numbers fill the last three positions in \(3!\) ways. So \(|A| = 2 \cdot 3! = 12\).
- \(|B|\). 5 is fixed in the last position, and the other four numbers fill the first four in any order: \(|B| = 4! = 24\).
- \(|A \cap B|\). 1 and 2 in front in 2 orders, 5 last, and 3 and 4 in the middle two positions in \(2!\) ways: \(|A \cap B| = 2 \cdot 2! = 4\).
By inclusion/exclusion,
\[|A \cup B| = |A| + |B| - |A \cap B| = 12 + 24 - 4 = 32,\]
and
\[P(A \cup B) = \frac{|A \cup B|}{5!} = \frac{32}{120} = \frac{4}{15} \approx 26.7\%.\]
Dividing the inclusion/exclusion identity through by \(120\) gives the same answer in terms of probabilities,
\[P(A \cup B) = P(A) + P(B) - P(A \cap B) = \frac{1}{10} + \frac{1}{5} - \frac{1}{30} = \frac{4}{15}.\]
Listing all 120 permutations and counting confirms 32. The four in \(A \cap B\) are 12345, 12435, 21345 and 21435, and adding \(12 + 24\) without subtracting them would count each of them twice.
Figure 9: Counting the permutations of \({1, \dots, 5}\) in \(A\), in \(B\) and in both, position by position. In \(A\), 1 and 2 take the first two positions in either order and the other three numbers fill the rest. In \(B\), 5 is fixed last and the other four are free. A permutation in both has all three restrictions, leaving only 3 and 4 to arrange in the middle.
See also
- inclusion-exclusion — the principle for two, three and \(n\) sets, why it counts each element once, “none of them” through the complement, counting multiples, and probabilities
- counting-principles — the addition rule for disjoint sets and the difference rule, which inclusion/exclusion extends
- probability — probability by counting equally likely outcomes, used in the last question
- 2026-10-19-probability-binomial-coefficients — Lecture 31 · 2026-10-22-pigeonhole-principle-introduction-to-graph-theory — Lecture 33
- practice-problems — §41, with full worked solutions