Inclusion-Exclusion

Count the size of a union of overlapping sets by adding and subtracting intersections systematically.

1. The idea

Inclusion-exclusion generalizes the two-set union formula to any number of sets: to count $∣ A_{1} \cup \dots \cup A_{n} ∣$ , sum the sizes of all single sets, subtract the sizes of all pairwise intersections, add back triple intersections, and so on, alternating signs.

It is the standard tool for 'at least one property holds' counting problems, and its complement form handles 'none of the properties hold,' which is often the more natural way to phrase constraints like 'no room is empty' or 'no letter is in its original position.'

A canonical application is counting surjections: the number of ways to assign $n$ distinguishable people to $k$ labeled rooms so that every room is non-empty uses inclusion-exclusion over the 'room $i$ is empty' events.

2. Why it matters

Inclusion-exclusion is the general-purpose tool behind derangements, surjection counts, and 'avoid this pattern' problems — recognizing when a direct count is contaminated by overlapping bad cases is a key interview skill.

3. Core mathematics

Two-set inclusion-exclusion

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

General inclusion-exclusion

i = 1 ⋃ n A_{i} = i \sum ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + i < j < k \sum ∣ A_{i} \cap A_{j} \cap A_{k} ∣ - \dots

Surjections from n elements onto k labeled sets

i = 0 \sum k (- 1)^{i} (i k) (k - i)^{n}

4. How to recognize it

Think of this when…

The problem asks to count outcomes where 'no room/box/person is empty' or 'at least one condition holds.'
You need to count elements satisfying at least one of several overlapping 'bad' properties.
A direct count would double-count overlaps between conditions.
The word 'surjection' or 'onto function' appears, or the setup describes it without naming it.

5. Worked example

Worked example

How many ways can 4 distinguishable people be assigned to 3 labeled rooms so that no room is empty?

1
Total assignments without restriction: each of 4 people picks one of 3 rooms.
$3^{4} = 81$
2
Let $A_{i}$ = assignments where room $i$ is empty. By inclusion-exclusion, subtract single-empty-room counts, add back double-empty-room counts.
$∣ A_{i} ∣ = 2^{4}, ∣ A_{i} \cap A_{j} ∣ = 1^{4}, ∣ A_{1} \cap A_{2} \cap A_{3} ∣ = 0$
3
Apply the surjection formula directly.
$i = 0 \sum 3 (- 1)^{i} (i 3) (3 - i)^{4} = 3^{4} - 3 (2^{4}) + 3 (1^{4}) - 0 = 81 - 48 + 3 = 36$
Answer: 36 ways.

6. Common mistakes

Forgetting to alternate signs (add, subtract, add, ...) across successive intersection orders.
Missing higher-order intersection terms when more than two sets overlap.
Confusing 'surjection count' (rooms non-empty) with plain 'function count' (each person picks any room, no restriction).
Sign errors or forgetting the binomial coefficient weighting the number of ways to choose which sets intersect.

7. Quick check

How many integers from 1 to 100 are divisible by 2 or 5?

How many onto functions are there from a 3-element set to a 2-element labeled set?

8. Practice

5 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Inclusion-Exclusion

Create a free account to save lesson progress.

Recommended next lessonDerangements →