Helpful context:

How many integers from 1 to 10 are divisible by 2 or 3?

The tempting approach: count multiples of 2 (there are 5: 2, 4, 6, 8, 10), count multiples of 3 (there are 3: 3, 6, 9), add them. Answer: 8.

Check against the actual list: 2, 3, 4, 6, 8, 9, 10. That is 7, not 8.

The individual counts are correct. The addition is wrong. The number 6 belongs to both groups, so it got counted twice - once as a multiple of 2 and again as a multiple of 3. Simple addition assumes the groups are disjoint. When they overlap, it overcounts.

This is the trap that inclusion-exclusion is designed to escape.

The Two-Set Fix

The overcounting is easy to correct for two groups. Whatever is in both groups got counted twice, so subtract it once:

$$|A \cup B| = |A| + |B| - |A \cap B|$$

In the example: $|A_2| = 5$, $|A_3| = 3$, and $|A_2 \cap A_3| = 1$ (only 6 is divisible by both 2 and 3 in this range). So $5 + 3 - 1 = 7$. ✓

The complement is immediate: numbers in neither group total $10 - 7 = 3$ (those are 1, 5, and 7).

Three Groups: The Subtraction Overshoots

Now add a third condition. How many integers from 1 to 30 are divisible by 2, 3, or 5?

Start the same way: add the three group sizes, then subtract pairwise overlaps.

$|A_2| = 15$, $|A_3| = 10$, $|A_5| = 6$. Sum: $31$.

Pairwise overlaps: $|A_2 \cap A_3| = \lfloor 30/6 \rfloor = 5$, $|A_2 \cap A_5| = \lfloor 30/10 \rfloor = 3$, $|A_3 \cap A_5| = \lfloor 30/15 \rfloor = 2$.

After subtracting: $31 - 5 - 3 - 2 = 21$.

The correct answer is 22. Something went wrong again.

The culprit is 30, which is divisible by all three. When we added the three groups, 30 was counted 3 times. When we subtracted the three pairwise overlaps, 30 appeared in all three pairs ($A_2 \cap A_3$, $A_2 \cap A_5$, $A_3 \cap A_5$) and was subtracted 3 times. Net count: $3 - 3 = 0$. We completely erased 30 from the tally.

The fix: add back the triple intersection. $|A_2 \cap A_3 \cap A_5| = \lfloor 30/30 \rfloor = 1$.

Final answer: $21 + 1 = 22$. ✓

multiples of 2, 3, and 5 in 1-30 — counts per region ÷ 2 ÷ 3 ÷ 5 8 4 2 4 2 1 1

Each region of the diagram holds a count: the number of integers in that exact combination of groups. Total: $8 + 4 + 2 + 4 + 2 + 1 + 1 = 22$. The formula reconstructs this total from the group and intersection sizes without needing to fill in every region individually.

Why the Alternating Pattern Is Self-Correcting

The add-subtract-add pattern is not a trick. It is a self-correcting mechanism, and the reason it works is precise.

Consider any element that belongs to exactly $k$ of the groups. Track how many times it appears in the alternating sum:

  • Adding all groups: counted $k$ times.
  • Subtracting pairwise overlaps: removed once for each pair of its groups - that is $\binom{k}{2}$ times.
  • Adding triple overlaps: added back $\binom{k}{3}$ times.
  • And so on.

Net count: $\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots = 1$ for any $k \geq 1$.

Walk through the concrete examples. The number 30 belongs to all three groups ($k = 3$): $3 - 3 + 1 = 1$. ✓ The number 6 belongs to two groups ($k = 2$): $2 - 1 = 1$. ✓ The number 4 belongs to one group ($k = 1$): $1$. ✓

Every element in the union ends up counted exactly once, regardless of how many groups it belongs to. Each correction introduces a new error in the opposite direction at the next level, and the alternation continues until all levels are exhausted. The result is perfect cancellation.

Why the corrections keep coming. When you add three groups, elements in all three are over-counted by 2. Subtracting pairwise overlaps corrects for that - but in doing so, it subtracts those elements 3 times, once too many. Adding the triple back corrects that - but if there were a quadruple overlap it would have been added back once too many times, requiring another subtraction. Each correction perturbs the next level. The alternation terminates only because the number of levels is finite.

Recognizing When to Use Inclusion-Exclusion

The principle applies whenever you want to count a union of overlapping groups and the groups share elements.

The “at least one” phrasing is the clearest signal: “passwords containing at least one digit,” “integers divisible by at least one of 2, 3, 5,” “permutations where at least one element is in its original position.” Each of these asks for the size of a union, and the groups can overlap.

The “none of” phrasing is its complement. “How many items satisfy none of these conditions?” is the total minus the union. Compute $|\text{total}| - |A_1 \cup \cdots \cup A_n|$. Derangements fall here: you want permutations avoiding the condition “element $i$ is in position $i$” for every $i$.

The test for whether inclusion-exclusion applies:

  1. Can you count “how many items satisfy condition $i$ alone” easily?
  2. Can you count “how many satisfy conditions $i$ and $j$ simultaneously”?
  3. Can conditions be satisfied together (do the groups overlap)?

If yes to all three, inclusion-exclusion is the right tool.

When you don’t need it: if the conditions are mutually exclusive (no item can satisfy two at once), simple addition suffices. Inclusion-exclusion reduces to ordinary addition when all intersections are empty.

The common mistake. With three or more overlapping groups, it is tempting to stop after “add groups, subtract pairwise overlaps.” This is incomplete. Subtracting pairwise overlaps removes elements in triple overlaps three times - once for each pair - erasing them entirely from the count. They must be added back via the triple intersection term. With four groups, quadruple overlaps must then be subtracted. The corrections always go one level deeper than the last.

The General Formula

For $n$ overlapping sets $A_1, A_2, \ldots, A_n$:

$$\left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \leq i_1 < \cdots < i_k \leq n} |A_{i_1} \cap \cdots \cap A_{i_k}|$$

Add all individual sizes. Subtract all pairwise intersection sizes. Add all triple intersection sizes. Continue, alternating signs, until all levels of overlap are accounted for.

Applications

Divisibility. How many integers from 1 to 1000 are divisible by at least one of 2, 3, or 5?

$|A_2| = 500$, $|A_3| = 333$, $|A_5| = 200$, $|A_2 \cap A_3| = 166$, $|A_2 \cap A_5| = 100$, $|A_3 \cap A_5| = 66$, $|A_2 \cap A_3 \cap A_5| = 33$.

$$500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$$

Numbers coprime to 30 (divisible by none of 2, 3, 5): $1000 - 734 = 266$.

Euler’s totient. $\phi(n)$ counts integers from 1 to $n$ that are coprime to $n$ - sharing no prime factor with $n$. This is exactly the divisibility argument above, but carried to its logical end.

Let $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$. An integer $k \in [1, n]$ is NOT coprime to $n$ if and only if it is divisible by at least one of the primes $p_1, \ldots, p_r$. So define:

$$A_i = \text{integers in } [1, n] \text{ divisible by } p_i$$

Then $\phi(n) = n - |A_1 \cup A_2 \cup \cdots \cup A_r|$.

Computing the intersection sizes. Since each $p_i$ is a prime factor of $n$, we have $p_i \mid n$, so the count of multiples of $p_i$ in $[1, n]$ is exactly $n/p_i$. For two distinct primes $p_i$ and $p_j$, a number is divisible by both iff it is divisible by $p_i p_j$ (distinct primes have no shared factors), giving $n/(p_i p_j)$ numbers. In general, any intersection of $k$ distinct prime conditions gives $n/(p_{i_1} \cdots p_{i_k})$ numbers.

Applying inclusion-exclusion. The union size is:

$$|A_1 \cup \cdots \cup A_r| = \sum_i \frac{n}{p_i} - \sum_{i < j} \frac{n}{p_i p_j} + \sum_{i < j < k} \frac{n}{p_i p_j p_k} - \cdots$$

Factor out $n$:

$$= n\left(\sum_i \frac{1}{p_i} - \sum_{i<j} \frac{1}{p_i p_j} + \sum_{i<j<k} \frac{1}{p_i p_j p_k} - \cdots\right)$$

So $\phi(n) = n - n(\ldots) = n \left(1 - \sum_i \frac{1}{p_i} + \sum_{i<j} \frac{1}{p_i p_j} - \cdots\right)$.

The product step. The expression in the parentheses is exactly the expansion of a product. Expanding $(1 - 1/p_1)(1 - 1/p_2)$ gives $1 - 1/p_1 - 1/p_2 + 1/(p_1 p_2)$. Multiplying by $(1 - 1/p_3)$ adds $-1/p_3 + 1/(p_1 p_3) + 1/(p_2 p_3) - 1/(p_1 p_2 p_3)$ to that. Each new factor contributes exactly the next level of inclusion-exclusion terms, with the alternating sign coming from the minus in $(1 - 1/p_i)$. After all $r$ factors:

$$1 - \sum_i \frac{1}{p_i} + \sum_{i<j} \frac{1}{p_i p_j} - \cdots = \prod_{i=1}^{r}\left(1 - \frac{1}{p_i}\right)$$

Therefore:

$$\phi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)$$

Worked example: $n = 30 = 2 \cdot 3 \cdot 5$.

The three prime conditions: divisible by 2, 3, or 5. The inclusion-exclusion sum written out:

$$30 - 15 - 10 - 6 + 5 + 3 + 2 - 1 = 8$$

The same calculation via the product formula:

$$\phi(30) = 30 \cdot \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right) = 30 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 8$$

The eight integers from 1 to 30 coprime to 30 are: 1, 7, 11, 13, 17, 19, 23, 29. These are exactly the numbers sharing no factor with $2 \cdot 3 \cdot 5$.

Note that the prime powers $p_i^{a_i}$ in $n$ do not appear in the formula - only the prime bases $p_i$ matter. Whether $n = 30$ or $n = 2^3 \cdot 3^2 \cdot 5 = 360$, the formula uses the same three factors $(1 - 1/2)(1 - 1/3)(1 - 1/5)$. The reason: divisibility by $p_i^2$ implies divisibility by $p_i$, so the higher powers add no new forbidden conditions beyond what $p_i$ already captures.

Passwords. How many 8-character passwords over $\{a\text{-}z, 0\text{-}9\}$ (36 characters total) contain at least one digit and at least one letter?

The complement: passwords missing digits or missing letters. Let $A$ = passwords with no digits ($26^8$ possibilities), $B$ = passwords with no letters ($10^8$ possibilities), $A \cap B = \emptyset$ (impossible to have neither).

Passwords missing at least one type: $26^8 + 10^8$. Passwords with both: $36^8 - 26^8 - 10^8 \approx 2.82 \times 10^{12}$.

Derangements. This is the “none of” version. Define $A_i$ = permutations where element $i$ is in its original position. A derangement avoids every $A_i$. The inclusion-exclusion formula gives $|A_1 \cup \cdots \cup A_n|$, and the derangement count is $n!$ minus that:

$$D_n = n!\left(1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right) \approx \frac{n!}{e}$$

Read next: