Inclusion–Exclusion

In one sentence

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

Why these seven terms, with these signs? Look at any single element. If it belongs to exactly $k$ of the sets ( $k \geq 1$ ), the formula counts it

(1 k) - (2 k) + (3 k) = 1 - (1 - 1)^{k} = 1

times: no more, no less, exactly once. The figure above spreads this out for you: each term you switch on adds one to, or takes one from, the “times counted” of the regions it covers.

Example: how many numbers from 1 to 100 are multiples of 2, 3 or 5?

Step 1 / 4

First add the single sets
$∣ A ∣ = 50$ , $∣ B ∣ = 33$ , $∣ C ∣ = 20$ . The regions where two sets overlap are counted $2$ times; the very middle is counted $3$ times.

$50 + 33 + 20 = 103$
Subtract the pairwise intersections
Add back the triple intersection
The other side

Predict first

After adding the three single sets and subtracting the three pairwise intersections, how many times in total has the region common to all three ( $A \cap B \cap C$ ) been counted?

Choose an answer first; then you can see the result.

Stop 1 · Operations on Sets (Vol. 1)

“Satisfies none of them” is the intersection $∁ A \cap ∁ B \cap ∁ C$ . By De Morgan's laws it equals $∁ (A \cup B \cup C)$ : count the union first, then subtract it from the universal set.

Example: how many numbers from 1 to 1000 are multiples of none of 2, 3 and 5?

Step 1 / 4

De Morgan
We are counting the intersection of three complements, which is the complement of the union.

$∁ A \cap ∁ B \cap ∁ C = ∁ (A \cup B \cup C)$
Single sets
Intersections
Take the complement

Stop 2 · Counting the Elements of a Finite Set (Vol. 1)

Count surjections: every element of the target is hit at least once. The opposite is “some element is never hit”, which is exactly what inclusion–exclusion does best.

Example: how many surjections are there from a 5-element set onto the 3-element set {a, b, c}?

Step 1 / 4

All mappings
Each element has $3$ places to go.

$3^{5} = 243$
Name the bad events
Inclusion–exclusion
Conclusion

Stop 3 · Inclusion–Exclusion and derangements (Vol. 1)

$n$ letters go into $n$ addressed envelopes. In how many ways can every letter go into the wrong envelope? That is the derangement number $D_{n}$ .

Example: find D₄

Step 1 / 4

Bad events
$A_{i}$ : letter $i$ is in the right envelope. A derangement is when none of the $A_{i}$ happens.

$∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣ = (4 - k)!$
Sum over k
Work it out
Conclusion

Practice

Exercise 1Basic

How many of $1, 2, \dots, 100$ are multiples of $3$ or multiples of $5$ ?

Exercise 2Advanced

How many of $1, 2, \dots, 200$ are divisible by none of $2, 3, 7$ ?

Exercise 3Advanced

$5$ people each write a greeting card. The cards are collected, shuffled and handed out, one per person. In how many ways can this happen so that nobody gets their own card?

Exercise 4Challenge

In how many ways can $4$ different balls be put into $3$ different boxes so that every box gets at least one ball?

Mistake Museum · Exhibits from this stop

Before you leave, look at the traps other people fell into here.See every exhibit in the museum →

Exhibit

Stopping after subtracting the pairwise intersections

Among

1 \sim 100

there are

50 + 33 + 20 - 16 - 10 - 6 = 71

multiples of

2

3

5

What went wrong? Think first, then open

Diagnosis When you add the three sets, the numbers that are multiples of all of $2, 3, 5$ ( $30, 60, 90$ ) are counted $3$ times; when you subtract the three pairwise intersections they are subtracted $3$ times. In the end they are not counted at all.

Add back the intersection of all three sets:

71 + 3 = 74

. The formula for three sets has seven terms, with signs alternating

+, -, +

“Added three times and subtracted three times means never counted”

Exhibit

Dividing by the wrong number for an intersection

Among

1 \sim 100

there are

[\frac{100}{24}] = 4

numbers that are multiples of both

4

and

6

What went wrong? Think first, then open

Diagnosis Being a multiple of both $4$ and $6$ means being a multiple of their least common multiple $12$ , not of their product $24$ . The number $12$ itself was missed.

There are

[\frac{100}{12}] = 8

. The lcm equals the product only when the two numbers are coprime.

“For an intersection, use the lcm”

In one sentence

Stop 1 · Operations on Sets (Vol. 1)

Stop 2 · Counting the Elements of a Finite Set (Vol. 1)

Stop 3 · Inclusion–Exclusion and derangements (Vol. 1)

Practice

Mistake Museum · Exhibits from this stop

Stops on this line