Inclusion/Exclusion
How to count a union of finite sets that overlap. The addition rule adds the sizes of sets only when they are disjoint; when an element can be in more than one set, adding the sizes counts it more than once. Inclusion/exclusion corrects this by subtracting the sizes of the pairwise intersections, adding back the triple intersections, and so on with alternating signs. This note covers 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 rule, the general rule for \(n\) sets, counting “none of them” through the complement, counting multiples with the floor function, and the same rule for probabilities. The addition and difference rules it extends are in counting-principles. First met in 2026-10-20-inclusion-exclusion.
Two sets
Inclusion/exclusion for two sets. For finite sets \(A\) and \(B\), \[|A \cup B| = |A| + |B| - |A \cap B|.\]
Why. Split \(A \cup B\) into three disjoint pieces: \(A - B\), \(A \cap B\) and \(B - A\). Then \(|A|\) counts the first two pieces and \(|B|\) counts the last two, so \(|A| + |B|\) counts \(A \cap B\) twice and the other two pieces once each. Subtracting \(|A \cap B|\) once leaves every element of the union counted once.
| \(A - B\) | \(A \cap B\) | \(B - A\) | |
|---|---|---|---|
| counted by \(\vert A\vert\) | 1 | 1 | 0 |
| counted by \(\vert B\vert\) | 0 | 1 | 1 |
| removed by \(-\vert A \cap B\vert\) | 0 | \(-1\) | 0 |
| total | 1 | 1 | 1 |
If \(A \cap B = \emptyset\), the correction is 0 and the rule is the addition rule, \(|A \cup B| = |A| + |B|\) (counting-principles). The three-piece split is also the quickest check on any two-set answer: once \(|A \cap B|\) is known, \(|A - B| = |A| - |A \cap B|\) and \(|B - A| = |B| - |A \cap B|\), and the pieces together with the outside must add to the size of the universe.
Figure 1: A universe \(U\) split by two sets into four disjoint regions. The circle \(A\) is the regions \(A - B\) and \(A \cap B\), and the circle \(B\) is \(A \cap B\) and \(B - A\), so the overlap is the one region inside both circles and is counted by both \(|A|\) and \(|B|\). Everything outside both circles is the complement \((A \cup B)^c\), the elements in neither set.
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 groups of terms, with alternating signs: the three single sets added, the three pairwise intersections subtracted, the one triple intersection added.
Figure 2: The eight disjoint regions into which three sets cut a universe \(U\), each named by which of \(A\), \(B\) and \(C\) it lies inside and which outside. Every term of the formula is a union of some of these regions: \(|A|\) covers the four regions inside \(A\), \(|A \cap B|\) the two inside both \(A\) and \(B\), and \(|A \cap B \cap C|\) the centre alone. The hatched region outside all three circles is \((A \cup B \cup C)^c = A^c \cap B^c \cap C^c\), the elements in none of the sets.
Every region counted once
Three overlapping circles make seven regions inside the union. Each region is described by how many of the three sets it lies in, and that number decides how the formula counts it.
- In exactly one set, say \(A\) only. Counted once by \(|A|\), and in none of the intersections. Net: 1.
- In exactly two sets, say \(A\) and \(B\) but not \(C\). Counted by \(|A|\) and \(|B|\), so twice, and removed once, by \(|A \cap B|\). It is not in \(A \cap C\) or \(B \cap C\), because those need \(C\). Net: \(2 - 1 = 1\).
- In all three. Counted three times by the singles, removed three times by the pairs, since it is in \(A \cap B\), \(A \cap C\) and \(B \cap C\), and added once by the triple. Net: \(3 - 3 + 1 = 1\).
This is why the triple intersection is added back once. After the pairs are subtracted, the centre has been counted \(3 - 3 = 0\) times, one short of the 1 it needs. Adding \(|A \cap B \cap C|\) twice would leave it counted twice.
Figure 3: Each region of a three-set Venn diagram labelled with how the formula counts it: the number of single sets containing it, minus the number of pairwise intersections containing it, plus the triple intersection if it is in all three. A region in one set is counted \(1\); a region in two sets \(2 - 1\); the centre \(3 - 3 + 1\). Every region comes to exactly 1.
Proving the three-set rule from the two-set rule
The three-set rule is three applications of the two-set rule, \(|X \cup Y| = |X| + |Y| - |X \cap Y|\), together with the set identities (formula-sheet).
\[\begin{aligned} |A \cup B \cup C| &= |A \cup (B \cup C)| && \text{associative law (2a)} \\ &= |A| + |B \cup C| - |A \cap (B \cup C)| && X = A,\ Y = B \cup C \\ &= |A| + |B| + |C| - |B \cap C| - |A \cap (B \cup C)| && X = B,\ Y = C \\ &= |A| + |B| + |C| - |B \cap C| - |(A \cap B) \cup (A \cap C)| && \text{distributive law (3b)} \\ &= |A| + |B| + |C| - |B \cap C| - \big(|A \cap B| + |A \cap C| - |A \cap B \cap C|\big) && X = A \cap B,\ Y = A \cap C \\ &= |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|. && \end{aligned}\]
The fifth line uses \((A \cap B) \cap (A \cap C) = A \cap B \cap C\), which is the commutative and associative laws (1b, 2b) to bring the two \(A\)’s together and the idempotent law (7b), \(A \cap A = A\). The triple term is subtracted inside a bracket that is itself subtracted, which is where its \(+\) sign comes from. Each step is drawn in 2026-10-20-inclusion-exclusion.
The same move, splitting off the last set and applying the two-set rule, proves the rule for four sets from the rule for three, and so on: it is an induction on \(n\) (mathematical-induction).
The general rule
Inclusion/exclusion for \(n\) sets. For finite sets \(A_1, A_2, \dots, A_n\), \[|A_1 \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 \cdots \cap A_n|.\]
Add the singles, subtract the pairs, add the triples, subtract the four-way intersections, and keep alternating up to the intersection of all \(n\), whose sign is \(+\) when \(n\) is odd and \(-\) when \(n\) is even. There are \(\binom{n}{k}\) intersections of \(k\) sets, so the formula has \(2^n - 1\) terms in all: 3 for two sets, 7 for three, 15 for four.
Written as a single sum over the non-empty sets \(S\) of indices, with \(\bigcap_{t \in S} A_t\) the intersection of the \(A_t\) for \(t \in S\) (for \(S = \{2, 3, 6\}\), that is \(A_2 \cap A_3 \cap A_6\)):
\[|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{\emptyset \neq S \subseteq \{1, \dots, n\}} (-1)^{|S|+1} \left| \bigcap_{t \in S} A_t \right|.\]
Why each element is counted once. Take an element \(x\) of the union, and say it lies in exactly \(m \geq 1\) of the sets. A term \(|\bigcap_{t \in S} A_t|\) counts \(x\) exactly when every set in \(S\) contains \(x\), that is, when \(S\) is a non-empty subset of the \(m\) indices of sets containing \(x\). There are \(\binom{m}{k}\) such \(S\) of size \(k\), so \(x\) is counted
\[\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m+1}\binom{m}{m} = 1 - (1 - 1)^m = 1\]
times. The middle step is the binomial theorem applied to \((1 - 1)^m = \sum_{k=0}^{m} \binom{m}{k}(-1)^k\), which is 0 because \(m \geq 1\) (binomial-coefficients). For \(m = 1, 2, 3, 4\) the counts are \(1\), \(2 - 1\), \(3 - 3 + 1\) and \(4 - 6 + 4 - 1\).
Figure 4: How the general formula counts an element lying in exactly \(m\) of the sets, for \(m = 1\) to \(5\). Row \(m\) lists \(\binom{m}{k}\), the number of intersections of \(k\) of those \(m\) sets, each carrying the sign of its group: \(+\) for odd \(k\) and \(-\) for even \(k\). The grey entry is \(\binom{m}{0} = 1\), which would belong to the empty set of indices and is not a term. Flipping the sign of every coloured entry and adding the grey 1 gives the expansion of \((1 - 1)^m = 0\), so the coloured entries themselves sum to \(1 - (1 - 1)^m = 1\) in every row.
None of them: the complement
Inclusion/exclusion counts the elements in at least one of the sets. The elements in none of them are everything else, so inside a universe \(U\),
\[|(A \cup B)^c| = |U| - |A \cup B| = |U| - |A| - |B| + |A \cap B|,\]
\[|(A \cup B \cup C)^c| = |U| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C| - |A \cap B \cap C|.\]
This is the difference rule (counting-principles) applied to the union. By De Morgan’s law (9a), \((A \cup B)^c = A^c \cap B^c\): “in neither \(A\) nor \(B\)” and “outside the union” are the same set. Questions phrased as “neither … nor”, “none of”, or “not divisible by any of” are complements of a union.
Figure 5: The elements in neither \(A\) nor \(B\). The part of \(U\) outside \(A\) and the part outside \(B\) overlap in exactly the region outside both circles, which is the complement of the union: \(A^c \cap B^c = (A \cup B)^c\). Counting that region is \(|U| - |A \cup B|\), and inclusion/exclusion supplies \(|A \cup B|\).
Running it backwards. The two-set rule links four numbers, \(|A|\), \(|B|\), \(|A \cap B|\) and \(|A \cup B|\), and any three determine the fourth. A question that gives the sizes of \(A\), \(B\) and the “neither” region, and asks for “both”, finds the union from the complement first and then solves for the intersection:
\[|A \cap B| = |A| + |B| - |A \cup B| = |A| + |B| - \big(|U| - |(A \cup B)^c|\big).\]
Counting multiples
The commonest use of inclusion/exclusion is counting integers with divisibility conditions. Two facts do all the work.
- The multiples of \(d\) in \(\{1, 2, \dots, N\}\) are \(d, 2d, \dots, kd\) for the largest \(k\) with \(kd \leq N\), that is, \(k \leq N/d\). So there are \(\lfloor N/d \rfloor\) of them. When \(d\) divides \(N\) the floor is not needed: \(105/3 = 35\).
- Being divisible by both \(a\) and \(b\) is being divisible by \(\operatorname{lcm}(a, b)\) (gcd-lcm-and-euclidean-algorithm). When \(a\) and \(b\) have no common factor, \(\operatorname{lcm}(a, b) = ab\), so the multiples of both 3 and 5 are the multiples of 15. When they share a factor it is smaller than \(ab\): the multiples of both 4 and 6 are the multiples of 12, not of 24.
The method, for “how many of \(1, \dots, N\) are divisible by none of \(a\), \(b\), \(c\)”:
- Let \(A\), \(B\), \(C\) be the multiples of \(a\), \(b\), \(c\) in \(\{1, \dots, N\}\).
- Count each with \(\lfloor N/d \rfloor\), using the lcm for each intersection.
- Combine with inclusion/exclusion to get \(|A \cup B \cup C|\).
- Subtract from \(N\).
Figure 6: The integers 1 to 30, with the multiples of 3 marked above the line and the multiples of 5 below. There are \(\lfloor 30/3 \rfloor = 10\) multiples of 3 and \(\lfloor 30/5 \rfloor = 6\) of 5, but 15 and 30, the multiples of \(\operatorname{lcm}(3, 5) = 15\), are marked twice. So \(10 + 6 - 2 = 14\) integers are divisible by 3 or 5, and the other 16 by neither.
With probabilities
When all outcomes in a finite sample space \(S\) are equally likely, \(P(E) = |E|/|S|\) (probability). Dividing the two-set rule through by \(|S|\) gives
\[P(A \cup B) = P(A) + P(B) - P(A \cap B),\]
and the three-set and \(n\)-set rules divide through in the same way. The probability that neither happens is \(1 - P(A \cup B)\). Either count first and divide at the end, or divide first and combine probabilities; the answer is the same.
Worked: divisible by 2, 3 or 5
How many of the integers \(1, 2, \dots, 1000\) are divisible by none of 2, 3 and 5?
Let \(A\), \(B\), \(C\) be the multiples of 2, 3 and 5 in \(\{1, \dots, 1000\}\). The numbers are pairwise coprime, so each intersection is the multiples of the product. Not every division is exact this time.
\[|A| = \left\lfloor \tfrac{1000}{2} \right\rfloor = 500, \quad |B| = \left\lfloor \tfrac{1000}{3} \right\rfloor = 333, \quad |C| = \left\lfloor \tfrac{1000}{5} \right\rfloor = 200,\]
\[|A \cap B| = \left\lfloor \tfrac{1000}{6} \right\rfloor = 166, \quad |A \cap C| = \left\lfloor \tfrac{1000}{10} \right\rfloor = 100, \quad |B \cap C| = \left\lfloor \tfrac{1000}{15} \right\rfloor = 66, \quad |A \cap B \cap C| = \left\lfloor \tfrac{1000}{30} \right\rfloor = 33.\]
\[|A \cup B \cup C| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734,\]
so \(1000 - 734 = 266\) are divisible by none of 2, 3 and 5. A direct count over \(1, \dots, 1000\) agrees.
Worked: the lcm, not the product
How many of the integers \(1, 2, \dots, 100\) are divisible by 4 or by 6?
Let \(A\) be the multiples of 4 and \(B\) the multiples of 6. Then \(|A| = \lfloor 100/4 \rfloor = 25\) and \(|B| = \lfloor 100/6 \rfloor = 16\). A number divisible by both 4 and 6 is divisible by \(\operatorname{lcm}(4, 6) = 12\), so \(|A \cap B| = \lfloor 100/12 \rfloor = 8\). Hence
\[|A \cup B| = 25 + 16 - 8 = 33.\]
Using \(4 \cdot 6 = 24\) for the intersection gives \(\lfloor 100/24 \rfloor = 4\) and the wrong answer 37. The number 12 is divisible by both 4 and 6 but not by 24.
Worked: both, from neither
In a class of 60 students, 35 study French, 28 study German and 10 study neither. How many study both?
Let \(F\) and \(G\) be the students studying French and German. The students studying at least one are everyone except the 10, so \(|F \cup G| = 60 - 10 = 50\). Then
\[|F \cap G| = |F| + |G| - |F \cup G| = 35 + 28 - 50 = 13.\]
Check: \(35 - 13 = 22\) French only, \(28 - 13 = 15\) German only, 13 both and 10 neither, and \(22 + 15 + 13 + 10 = 60\).
Worked: at least one six
Two fair dice are rolled. What is the probability that at least one shows a six?
The 36 ordered pairs of results are equally likely. Let \(A\) be “the first die shows 6” and \(B\) “the second die shows 6”. Each has 6 outcomes, and \(A \cap B\) is the single outcome \((6, 6)\). So
\[P(A \cup B) = P(A) + P(B) - P(A \cap B) = \frac{6}{36} + \frac{6}{36} - \frac{1}{36} = \frac{11}{36}.\]
The answer \(\frac{12}{36} = \frac13\), from adding without the correction, counts the double six twice. The complement agrees: no six on either die has \(5 \cdot 5 = 25\) outcomes, and \(1 - \frac{25}{36} = \frac{11}{36}\).
Common mistakes
- Adding overlapping sets. \(|A| + |B|\) is \(|A \cup B|\) only when \(A\) and \(B\) are disjoint. Otherwise it counts every element of \(A \cap B\) twice.
- The wrong sign on the triple term. \(|A \cap B \cap C|\) is added. Subtracting it, as if every intersection were subtracted, leaves the centre counted \(3 - 3 - 1 = -1\) times.
- Leaving out the triple term. Subtracting the three pairs and stopping counts the centre 0 times.
- “Neither” as \(|U| - |A| - |B|\). That removes \(A \cap B\) twice. The elements in neither are \(|U| - |A \cup B| = |U| - |A| - |B| + |A \cap B|\).
- The product instead of the lcm. Divisible by 4 and 6 is divisible by 12, not 24. The product is right only when the numbers share no factor.
- Forgetting the floor. There are \(\lfloor 1000/3 \rfloor = 333\) multiples of 3 up to 1000, not \(333.\overline{3}\).
- Including the empty set of indices. In the sum over index sets \(S\), \(S\) ranges over the non-empty subsets of \(\{1, \dots, n\}\). There is no intersection of no sets among the terms.
- Reading the “neither” group wrongly. “Came to class and scored below 60%” is outside both “did not come” and “scored at least 60%”: it is \((A \cup B)^c\), not \(A \cap B\) or \(A^c\) alone.
See also
- 2026-10-20-inclusion-exclusion — Lecture 32, with every question worked in full
- counting-principles — the addition rule for disjoint sets and the difference rule
- sets-and-set-notation — unions, intersections and complements
- formula-sheet — the numbered set identities used in the proof
- gcd-lcm-and-euclidean-algorithm — the lcm, for intersections of sets of multiples
- binomial-coefficients — \(\binom{m}{k}\) and the binomial theorem behind the general rule
- probability — probability by counting equally likely outcomes
- practice-problems — §41, with full worked solutions