Inclusion–Exclusion

In one sentence

When several sets are pairwise disjoint, the size of their union is the sum of their sizes (the addition principle). When they overlap, the overlaps are counted too often and must be subtracted; if you subtract too much, add it back:

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

This is the inclusion–exclusion principle. The workbench above marks how many times each region has been counted: the formula is right exactly when every region is counted $1$ time.

Why every region is counted exactly once

Step 1 / 4

Add everything first
$∣ A ∣ + ∣ B ∣ + ∣ C ∣$ : regions inside one circle are counted $1$ time, regions inside two circles $2$ times, and the middle $3$ times.

$∣ A ∣ + ∣ B ∣ + ∣ C ∣$
Subtract the pairwise intersections
Add back the triple intersection
Any number of sets

Stop 1 · Integers: counting “none of them”

How many numbers in $1 \sim 60$ are coprime to $30$ ? Being coprime to $30$ means being a multiple of neither $2$ , nor $3$ , nor $5$ : the region outside all the circles. Above, the circles hold $44$ numbers, so the outside has $60 - 44 = 16$ .

Predict first

How many numbers in $1 \sim 100$ are multiples of neither $2$ , nor $3$ , nor $5$ ?

numbers

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

Stop 2 · Permutations: derangements

$4$ letters go into $4$ addressed envelopes, every letter in a wrong envelope. In how many ways can this happen?

Counting derangements by inclusion–exclusion

Step 1 / 4

Set up the sets
There are $4! = 24$ ways to fill the envelopes. Let $A_{i}$ be the ways in which letter $i$ is in the right envelope. We want the ways that lie in none of the $A_{i}$ .

$24 - ∣ A_{1} \cup A_{2} \cup A_{3} \cup A_{4} ∣$
The size of each term
Inclusion–exclusion
Take the complement

Stop 3 · Mappings: no empty box

In how many ways can $5$ different balls go into $3$ different boxes with no box empty? Two ways of thinking, and the answers must agree:

One problem, several solutions

$5$ different balls go into $3$ different boxes with no box empty. Count the ways.

Inclusion–exclusion: remove the ways with an empty box

Without restrictions there are $3^{5} = 243$ ways. Let $A_{i}$ be “box $i$ is empty”: $∣ A_{i} ∣ = 2^{5} = 32$ , $∣ A_{i} \cap A_{j} ∣ = 1$ , and all three empty is impossible.

The ways with an empty box number $3 \times 32 - 3 \times 1 + 0 = 93$ , so the ways with no empty box number $243 - 93 = 150$ .

CostMechanical, and works just as well for $n$ balls and $m$ boxes.

Partitions: group first, then assign

First split the $5$ balls into $3$ non-empty groups: $S (5, 3) = 25$ ways (an exercise in station 4). Then hand the $3$ groups to the $3$ boxes: $3! = 6$ ways.

In all, $25 \times 6 = 150$ ways.

CostYou need to count partitions first (station 4), but the structure is clearer.

Practice

Exercise 1Basic

How many numbers in $1 \sim 120$ are multiples of $2$ or multiples of $3$ ?

Exercise 2Basic

A class has $40$ students. $25$ are in the math club, $20$ are in the physics club, and $8$ are in neither. How many are in both?

Exercise 3Advanced

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

Exercise 4Challenge

In how many ways can $6$ different balls go into $3$ different boxes with no box empty?

In one sentence

Why every region is counted exactly once

Stop 1 · Integers: counting “none of them”

Stop 2 · Permutations: derangements

Counting derangements by inclusion–exclusion

Stop 3 · Mappings: no empty box

Inclusion–exclusion: remove the ways with an empty box

Partitions: group first, then assign

Practice

Mistake Museum · Exhibits from this stop

Stopping after subtracting the pairwise intersections

Counting “neither” and stopping after subtracting