Intermediate20 min

Inclusion–Exclusion and Pigeonhole

Counting unions of overlapping sets, derangements, and the pigeonhole principle as a proof device.

Assumes you know

Counting, Permutations and Combinations

Inclusion–Exclusion and Pigeonhole

Intuition first

Two counting principles that look almost trivial and repeatedly settle problems that resist direct attack.

Inclusion–exclusion fixes double counting. If 30 students take maths and 25 take physics, the number taking at least one is not 55 unless nobody takes both. Subtract the overlap. With three sets you subtract the pairwise overlaps and then have to add back the triple overlap, because subtracting the pairs removed it too many times. The alternating pattern continues for any number of sets.

Pigeonhole is even simpler: put 13 people in a room and two share a birth month, because there are only 12 months. No cleverness, just arithmetic — and it proves existence results that would otherwise be hard, precisely because it needs no construction.

Inclusion–exclusion

Two sets:

\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert

Three sets:

\lvert A \cup B \cup C \rvert = \lvert A \rvert + \lvert B \rvert + \lvert C \rvert - \lvert A \cap B \rvert - \lvert A \cap C \rvert - \lvert B \cap C \rvert + \lvert A \cap B \cap C \rvert

In general, for $n$ sets:

\left\lvert \bigcup_{i=1}^{n} A_i \right\rvert = \sum_{\varnothing \neq S \subseteq \{1..n\}} (-1)^{\lvert S \rvert + 1}\left\lvert \bigcap_{i \in S} A_i \right\rvert

Why the alternating signs are exactly rightAdvanced

Take an element belonging to exactly $k$ of the sets, $k \geq 1$ . It should be counted once in the union. Count how many times the formula counts it.

It appears in $\binom{k}{1}$ single sets, $\binom{k}{2}$ pairwise intersections, $\binom{k}{3}$ triples, and so on. With the alternating signs its total contribution is

\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \dots + (-1)^{k+1}\binom{k}{k} = \sum_{j=1}^{k}(-1)^{j+1}\binom{k}{j}

Now recall the binomial expansion of $(1 - 1)^k$ :

0 = (1-1)^k = \sum_{j=0}^{k}(-1)^j \binom{k}{j} = \binom{k}{0} - \binom{k}{1} + \binom{k}{2} - \dots

Since $\binom{k}{0} = 1$ , rearranging gives

\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \dots = 1

So every element in at least one set is counted exactly once, regardless of $k$ . Elements in no set contribute nothing. The formula is exact.

The probability version is identical with $\lvert \cdot \rvert$ replaced by $\Prob$ .

Solved problem 1 · Three languages

Of 100 students: 45 study French, 38 German, 30 Spanish; 18 study French and German, 12 French and Spanish, 10 German and Spanish, and 5 study all three. How many study none?

Step 1 — apply the three-set formula

\lvert F \cup G \cup S \rvert = 45 + 38 + 30 - 18 - 12 - 10 + 5

Step 2 — evaluate in stages

45 + 38 + 30 = 113

113 - 18 - 12 - 10 = 113 - 40 = 73

73 + 5 = 78

Step 3 — take the complement

100 - 78 = 22

Step 4 — verify with a region-by-region breakdown

Compute each disjoint region and check the total.

All three: 5.

Exactly two:

F\cap G \text{ only}: 18 - 5 = 13, \quad F \cap S \text{ only}: 12 - 5 = 7, \quad G \cap S \text{ only}: 10 - 5 = 5

Exactly one:

F \text{ only}: 45 - 13 - 7 - 5 = 20

G \text{ only}: 38 - 13 - 5 - 5 = 15

S \text{ only}: 30 - 7 - 5 - 5 = 13

Sum:

20 + 15 + 13 + 13 + 7 + 5 + 5 = 78 \;\checkmark

Answer

$78$ students study at least one language, so $22$ study none.

Derangements

A derangement is a permutation with no fixed point — nothing in its original position. Let $D_n$ be the number of derangements of $n$ items.

Counting derangements by inclusion–exclusionAdvanced

Let $A_i$ be the set of permutations fixing item $i$ . We want permutations in none of the $A_i$ , which is the complement of their union.

Fixing a specific set of $j$ items leaves the other $n - j$ free, so any such intersection has $(n-j)!$ permutations, and there are $\binom{n}{j}$ ways to choose which $j$ are fixed:

\left\lvert \bigcup_i A_i \right\rvert = \sum_{j=1}^{n}(-1)^{j+1}\binom{n}{j}(n-j)!

Therefore

D_n = n! - \left\lvert \bigcup_i A_i \right\rvert = \sum_{j=0}^{n}(-1)^j \binom{n}{j}(n-j)!

Expand $\binom{n}{j}(n-j)! = \frac{n!}{j!}$ :

D_n = n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}

The sum is the truncated series for $e^{-1}$ , so

\frac{D_n}{n!} \;\longrightarrow\; e^{-1} \approx 0.3679

The probability that a random permutation has no fixed point converges to $1/e$ — and does so fast: it is already accurate to four decimal places at $n = 7$ . Notably, this limit does not depend on $n$ , which pairs with the earlier result that the expected number of fixed points is exactly 1 for every $n$ .

Solved problem 2 · The hat-check problem

Five people leave hats at a cloakroom and receive them back at random. What is the probability nobody gets their own hat?

Step 1 — total outcomes

5! = 120

Step 2 — count derangements using the formula

D_5 = 5!\left(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}\right)

Evaluate the bracket:

1 - 1 + 0.5 - 0.166667 + 0.041667 - 0.008333 = 0.366667

D_5 = 120 \times 0.366667 = 44

Step 3 — the probability

\Prob(\text{no one gets their hat}) = \frac{44}{120} = \frac{11}{30} \approx 0.3667

Step 4 — compare with the limit

e^{-1} \approx 0.36788

At $n = 5$ the exact answer $0.36667$ is already within $0.0012$ of the limit.

Answer

$\dfrac{11}{30} \approx 0.3667$ , very close to $1/e$ .

The pigeonhole principle

Basic form. If $n$ items go into $m$ containers and $n > m$ , some container holds at least two items.

Generalised form. With $n$ items in $m$ containers, some container holds at least $\lceil n/m \rceil$ items.

Solved problem 3 · Two applications

(a) In any group of 13 people, two share a birth month. (b) In any set of 5 points inside a unit square, two are within distance $\frac{\sqrt{2}}{2}$ .

(a) — identify items and containers

Items: 13 people. Containers: 12 months. Since $13 > 12$ , some month holds at least two people.

The generalised form gives $\lceil 13/12 \rceil = 2$ , the same conclusion.

(b) — construct the containers

Divide the unit square into four sub-squares of side $\tfrac12$ by cutting at the midpoints.

With 5 points in 4 sub-squares, some sub-square contains at least $\lceil 5/4 \rceil = 2$ points.

(b) — bound the distance within a sub-square

The largest distance inside a square of side $s$ is its diagonal, $s\sqrt{2}$ . Here $s = \tfrac12$ :

\text{max distance} = \frac{\sqrt{2}}{2} \approx 0.7071

So those two points are at most $\frac{\sqrt{2}}{2}$ apart.

Answer

Both follow immediately once the containers are chosen well. Choosing the containers is the creative step — the principle itself is arithmetic.

python

from math import comb, factorial, exp, ceil

# Three languages.
union = 45 + 38 + 30 - 18 - 12 - 10 + 5
print(f"at least one: {union}   none: {100 - union}")

# Derangements, two ways.
def derangements(n):
    return sum((-1)**j * comb(n, j) * factorial(n - j) for j in range(n + 1))

print(f"\n{'n':>3} {'D_n':>10} {'D_n/n!':>10} {'1/e':>10}")
for n in range(1, 11):
    d = derangements(n)
    print(f"{n:3d} {d:10d} {d/factorial(n):10.6f} {exp(-1):10.6f}")

# Pigeonhole: guaranteed minimum occupancy.
for items, containers in ((13, 12), (5, 4), (100, 7)):
    print(f"\n{items} items in {containers} containers "
          f"-> some container has >= {ceil(items/containers)}")

Exercise 1

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

Show solution

Let $A_2, A_3, A_5$ be the multiples of 2, 3 and 5. Counts use floor division:

\lvert A_2 \rvert = \lfloor 100/2 \rfloor = 50, \quad \lvert A_3 \rvert = 33, \quad \lvert A_5 \rvert = 20

Pairwise intersections are multiples of the products:

\lvert A_2 \cap A_3 \rvert = \lfloor 100/6 \rfloor = 16, \quad \lvert A_2 \cap A_5 \rvert = \lfloor 100/10 \rfloor = 10, \quad \lvert A_3 \cap A_5 \rvert = \lfloor 100/15 \rfloor = 6

Triple intersection, multiples of 30:

\lvert A_2 \cap A_3 \cap A_5 \rvert = \lfloor 100/30 \rfloor = 3

Apply the formula:

50 + 33 + 20 - 16 - 10 - 6 + 3 = 103 - 32 + 3 = 74

74 integers. So 26 are coprime to 30 — which matches Euler's totient reasoning: $100 \times \tfrac12 \times \tfrac23 \times \tfrac45 = 26.67$ , close since 100 is not an exact multiple of 30.

Exercise 2

Show that among any 5 integers, some pair has a difference divisible by 4.

Show solution

Consider each integer's remainder on division by 4. There are exactly four possible remainders: $0, 1, 2, 3$ — these are the containers.

With 5 integers and 4 remainder classes, pigeonhole guarantees two integers $a$ and $b$ share a remainder $r$ :

a = 4q_1 + r, \qquad b = 4q_2 + r

Their difference is

a - b = 4(q_1 - q_2)

which is divisible by 4.

The argument generalises directly: among any $n+1$ integers, some pair has a difference divisible by $n$ . Note again that it identifies no particular pair — only that one exists.

Next: Geometric, Negative Binomial and Hypergeometric.