Math Core

Inclusion-exclusion is the tool for "none of these bad things happens" and "every one of these things happens." At the AIME level you use it with many conditions at once, and the trick is organizing the terms so that each one is a simple count.

The general formula

For sets $A_1, A_2, \dots, A_n$ ,

$|A_1 \cup \dots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \dots$

Each element that lies in exactly $r \ge 1$ of the sets is counted $\binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \dots = 1$ time, which is why the formula works.

In practice you almost always want the complement: the number of objects with none of the bad properties.

Inclusion-exclusion for 'none'

If $N$ objects are in total, and $A_1, \dots, A_n$ are the sets of objects with each bad property, then

$\#\{\text{none}\} = N - S_1 + S_2 - S_3 + \dots + (-1)^n S_n,$

where $S_k$ is the sum of $|A_{i_1} \cap \dots \cap A_{i_k}|$ over all choices of $k$ of the sets.

When the problem is symmetric, every intersection of $k$ sets has the same size $s_k$ , and $S_k = \dbinom{n}{k} s_k$ .

Symmetry is what makes AIME problems workable. With $8$ conditions you would never list $255$ intersections, but if they all look alike you only need one count per $k$ .

Three standard families

Derangements. A permutation of $n$ objects with no fixed points is a derangement. Let $A_i$ be the permutations fixing object $i$ . Fixing $k$ specific objects leaves $(n - k)!$ permutations, so

$D_n = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n - k)! = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \dots + \frac{(-1)^n}{n!}\right).$

The first values are $D_1 = 0$ , $D_2 = 1$ , $D_3 = 2$ , $D_4 = 9$ , $D_5 = 44$ , $D_6 = 265$ , $D_7 = 1854$ . They also satisfy $D_n = (n - 1)(D_{n-1} + D_{n-2})$ .

To count permutations with exactly $j$ fixed points, choose which $j$ are fixed and derange the rest: $\dbinom{n}{j} D_{n - j}$ .

Surjections. The number of functions from an $m$ -element set onto a $k$ -element set (every output used) is

$\sum_{i=0}^{k} (-1)^i \binom{k}{i} (k - i)^m.$

Here $A_i$ is the set of functions that miss output $i$ .

Bounded stars and bars. To count solutions of $x_1 + \dots + x_k = n$ with upper bounds, let $A_i$ be the solutions with $x_i$ too big. Shifting $x_i$ down turns each intersection into an ordinary stars-and-bars count.

Common mistake

Don't stop after subtracting the singles. Objects with two bad properties were subtracted twice and must be added back, and so on. If your answer is negative or suspiciously small, you probably forgot a term.

Worked example: Divisibility

How many integers from $1$ to $1000$ are divisible by none of $2$ , $3$ , $5$ ?

Use $\left\lfloor 1000/d \right\rfloor$ for the multiples of $d$ :

$1000 - (500 + 333 + 200) + (166 + 100 + 66) - 33 = 266.$

The pair terms use $6$ , $10$ , $15$ and the triple term uses $30$ .

Worked example: Exactly two fixed points

Six letters are placed at random into six addressed envelopes, one per envelope. The probability that exactly two letters land in their correct envelopes is $\dfrac{m}{n}$ in lowest terms. Find $m + n$ .

Choose the two correct letters in $\dbinom{6}{2} = 15$ ways; the other four must be deranged, in $D_4 = 9$ ways. The probability is $\dfrac{15 \cdot 9}{720} = \dfrac{135}{720} = \dfrac{3}{16}$ , so $m + n = 19$ .

Worked example: Every worker gets a job

In how many ways can $6$ different tasks be assigned to $3$ workers so that every worker gets at least one task?

All assignments: $3^6 = 729$ . Missing a given worker: $2^6 = 64$ , for each of $3$ workers. Missing two given workers: $1$ , for each of $3$ pairs. So the count is $729 - 3 \cdot 64 + 3 \cdot 1 = 540$ .

Worked example: Couples not side by side

Four married couples sit in a row of $8$ chairs in random order. The probability that no husband sits next to his wife is $\dfrac{m}{n}$ in lowest terms. Find $m + n$ .

Let $A_i$ be the seatings where couple $i$ sits together. For $k$ specific couples together, glue each into a block: $(8 - k)!$ orders of the units, times $2^k$ for the order inside each block. So

$\sum_{k=0}^{4} (-1)^k \binom{4}{k} 2^k (8 - k)! = 40320 - 40320 + 17280 - 3840 + 384 = 13824.$

The probability is $\dfrac{13824}{40320} = \dfrac{12}{35}$ , so $m + n = 47$ .

Tip

Before computing, write the answer as $\sum (-1)^k \binom{n}{k} s_k$ and find a formula for $s_k$ . If you can't describe $s_k$ in one line, rethink what your sets $A_i$ are.