Math Core

When you count the members of overlapping groups by adding the group sizes, anything in two groups gets counted twice. Inclusion-exclusion is the bookkeeping that fixes this: add the singles, subtract the doubles, add back the triples, and so on. It's the engine behind derangements, "every box nonempty" problems, and upper bounds in stars and bars.

Two and three sets

For two sets, an element in both $A$ and $B$ is counted twice by $|A| + |B|$ , so subtract it once:

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

For three sets, draw the Venn diagram.

Three overlapping sets. The center region lies in all three.

Adding $|A| + |B| + |C|$ counts each two-set region twice and the center three times. Subtracting the three pairwise intersections removes the double counts, but it also removes the center three times, leaving it counted $0$ times. So add it back once:

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

Inclusion-exclusion

To count elements with at least one of several properties, add the sizes of the single sets, subtract the sizes of all pairwise intersections, add all triple intersections, subtract all quadruple intersections, and so on, alternating signs.

To count elements with none of the properties, subtract that from the total:

$\#(\text{none}) = N - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + \cdots$

Why it works. Take an element that has exactly $m \ge 1$ of the properties. It is counted $\dbinom{m}{1}$ times in the singles, $\dbinom{m}{2}$ times in the pairs, and so on. Its net count is

$\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots = 1,$

because $\dbinom{m}{0} - \dbinom{m}{1} + \dbinom{m}{2} - \cdots = (1 - 1)^m = 0$ . Every element is counted exactly once.

The symmetric shortcut

In contest problems the sets are usually symmetric: every single set has the same size, every pair has the same intersection size, and so on. Then with $n$ properties,

$\#(\text{none}) = N - \binom{n}{1}S_1 + \binom{n}{2}S_2 - \binom{n}{3}S_3 + \cdots$

where $S_k$ is the size of any one $k$ -fold intersection. The work is just computing $S_1, S_2, \dots$ .

Worked example: Divisibility

How many integers from $1$ to $1000$ are divisible by $3$ , $5$ , or $7$ ?

Count multiples with floors: $\lfloor 1000/3 \rfloor = 333$ , $\lfloor 1000/5 \rfloor = 200$ , $\lfloor 1000/7 \rfloor = 142$ . The pairwise intersections are multiples of $15$ , $21$ , $35$ : $66$ , $47$ , $28$ . Multiples of $105$ : $9$ .

$333 + 200 + 142 - 66 - 47 - 28 + 9 = 543.$

Worked example: Derangements

Five people check their hats, and the hats are handed back at random. In how many of the $5! = 120$ ways does nobody get their own hat?

Let $A_i$ be the arrangements where person $i$ gets their own hat. Fixing any $k$ specific people leaves $(5 - k)!$ arrangements of the rest. So

$D_5 = 5! - \binom{5}{1}4! + \binom{5}{2}3! - \binom{5}{3}2! + \binom{5}{4}1! - \binom{5}{5}0! = 120 - 120 + 60 - 20 + 5 - 1 = 44.$

The general pattern is $D_n = n!\left(1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \cdots + \dfrac{(-1)^n}{n!}\right)$ . Worth memorizing: $D_1 = 0$ , $D_2 = 1$ , $D_3 = 2$ , $D_4 = 9$ , $D_5 = 44$ , $D_6 = 265$ .

Worked example: No empty box

In how many ways can $5$ different balls be placed into $3$ different boxes so that no box is empty?

Total: $3^5 = 243$ . Let $A_i$ be the placements where box $i$ is empty. One specific box empty: $2^5 = 32$ . Two specific boxes empty: $1^5 = 1$ . All three empty: $0$ .

$243 - \binom{3}{1}32 + \binom{3}{2}1 = 243 - 96 + 3 = 150.$

Common mistake

The most common error is stopping after the subtraction step. In the example above, $243 - 96 = 147$ is wrong: the placements with all balls in one box were subtracted twice (once for each empty box) and must be added back. Always ask, "what did I subtract more than once?"

Worked example: No two identical letters adjacent

How many arrangements of AABBCC have no two identical letters next to each other?

Total: $\dfrac{6!}{2!\,2!\,2!} = 90$ . Let $A$ be the arrangements with the two A's adjacent, and similarly $B$ and $C$ .

One pair glued (say AA as a block): arrange AA, B, B, C, C, giving $\dfrac{5!}{2!\,2!} = 30$ .
Two pairs glued: arrange AA, BB, C, C, giving $\dfrac{4!}{2!} = 12$ .
All three glued: $3! = 6$ .

$90 - 3 \cdot 30 + 3 \cdot 12 - 6 = 30.$

Practice

Practice 1

How many integers from $1$ to $500$ are divisible by neither $2$ nor $3$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 2

In a class of $40$ students, $25$ play soccer, $18$ play basketball, and $7$ play neither. How many play both?

Practice 3

How many integers from $1$ to $1000$ are neither perfect squares nor perfect cubes?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 4

Six letters are placed at random into six addressed envelopes, one per envelope. In how many of the $720$ ways do exactly two letters land in their correct envelopes?

Practice 5

Six students are assigned to three different project rooms. Each student goes to one room, and each room must get at least one student. How many assignments are possible?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 6

How many strings of $5$ digits (each from $0$ to $9$ , leading zeros allowed) contain at least one $1$ , at least one $2$ , and at least one $3$ ?

Practice 7

How many integers from $1$ to $210$ share no prime factor with $210$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 8

How many solutions does $x_1 + x_2 + x_3 + x_4 = 20$ have in nonnegative integers with every $x_i \le 7$ ?

Practice 9

Four married couples sit in a row of $8$ chairs. In how many seatings does no one sit next to their spouse?

Real contest practice

2021 AMC 10B, Problem 22: a probability that at least one box gets matching colors, solved with inclusion-exclusion.
2015 AMC 12A: Problem 17 asks for the chance that no two neighbors at a round table both stand. Try it by subtracting the "some adjacent pair stands" outcomes with inclusion-exclusion.