Inclusion–exclusion, derangements and the pigeonhole

Two techniques cover most of the counting problems that look hard. Inclusion–exclusion handles overlapping conditions, and its standard cue is the phrase "at least one". Pigeonhole and parity handle the questions that ask you to prove something *cannot* happen, which is a different kind of answer and needs a different reflex.

Equation 3.1

Inclusion–exclusion

Add the singles, subtract the pairs, add the triples, alternating. Each element ends up counted exactly once.

\left|\bigcup_{i=1}^{n} A_i\right| = \sum |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots

$A_i$: The set of outcomes satisfying the $i$ -th condition.

Proposition 3.2

Take the complement first

When a problem says "at least one", the complement — "none" — is almost always the easier count. For independent conditions, $P(\text{at least one}) = 1 - \prod(1 - p_i)$ , and you have avoided inclusion–exclusion entirely. Reach for the full alternating sum only when the conditions genuinely interact.

Holds when

The birthday problem, the coupon collector and "at least one six in four rolls" all yield to the complement in one line.
Inclusion–exclusion earns its keep when the events are structurally linked, as in derangements.

Both A and B — 10 of 100
A only — 30 of 100
B only — 20 of 100
Neither — 40 of 100

Figure 3.3 · Where the overlap goes when you count A or B. A covers 40 outcomes and B covers 30, but 10 satisfy both. Adding 40 + 30 counts those 10 twice, so subtract the overlap once: the union contains 60 of the 100 outcomes.

Derivation 3.4

Derangements — the hat-check problem

How many permutations of $n$ items leave nothing in its own place?

$|A_i| = (n-1)! \text{ where } A_i \text{ fixes item } i$
Pin one item and permute the rest.
$\left|\bigcup A_i\right| = \sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}(n-k)!$
Inclusion–exclusion over which items are fixed.
$D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$
Subtract from the total and simplify.

D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} \ \longrightarrow\ \frac{n!}{e}

Why the answer is $1/e$ . The probability that a random permutation is a derangement tends to $1/e \approx 0.3679$ , and it does so almost immediately: at $n = 4$ it is already $0.375$ , and at $n = 7$ it matches to four decimals. The reason is that each item fails to be fixed with probability roughly $1 - 1/n$ , and $(1-1/n)^n \to e^{-1}$ . The near-independence of the events is what makes a Poisson-style limit appear, and it is why the number of fixed points of a random permutation is approximately Poisson with mean one.

Example 3.5

Five traders hang up five identical-looking coats and each takes one at random. What is the probability nobody gets their own?

Show the worked solutionHide the worked solution

Worked solution

Formula $P = \frac{D_n}{n!} = \sum_{k=0}^{n}\frac{(-1)^k}{k!}$
Substitute $= 1 - 1 + \tfrac12 - \tfrac16 + \tfrac1{24} - \tfrac1{120}$
Solve $= \frac{60 - 20 + 5 - 1}{120} = \frac{44}{120}$
$D_5 = 44$
Answer $P = \frac{44}{120} \approx 36.7\%$

Sanity check. Within $0.002$ of $1/e = 0.3679$ at only five items, which is the point of the intuition above.

Inclusion–exclusion, derangements and the pigeonhole

After this lesson you should be able to