Inclusion--exclusion: why the alternating signs work

The inclusion--exclusion principle corrects for overcounting by alternately adding and subtracting intersection sizes. We prove the general formula using indicator functions, apply it to count derangements, and trace the thread forward to the Mobius inversion formula on partially ordered sets.

Folio Official

March 1, 2026

The inclusion–exclusion principle instructs us to add, subtract, add again, subtract again – an operation that seems almost whimsical. For two sets and a Venn diagram the logic is intuitive, but as the number of sets grows to three, four, or more, why does this alternating pattern of signs continue to yield the correct count? Where does the cancellation come from?

1 Two sets: the Venn diagram

Theorem 1 (Inclusion–exclusion for two sets).

For finite sets

A

and

B

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

A glance at a Venn diagram makes this self-evident. The sum $∣ A ∣ + ∣ B ∣$ counts every element of $A \cap B$ twice, so we subtract $∣ A \cap B ∣$ once to correct the overcount.

2 The general formula

Theorem 2 (Inclusion–exclusion, general form).

For finite sets

A_{1}, A_{2}, \dots, A_{n}

i = 1 ⋃ n A_{i} = k = 1 \sum n (- 1)^{k + 1} ∣ S ∣ = k \sum i \in S ⋂ A_{i}

where

S

ranges over all non-empty subsets of

{1, 2, \dots, n}

Written out explicitly:

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 + (- 1)^{n + 1} ∣ A_{1} \cap \dots \cap A_{n} ∣.

3 Proof via indicator functions

Proof.

Fix an arbitrary element

x \in ⋃_{i = 1}^{n} A_{i}

. Suppose

x

belongs to exactly

m

of the sets, say

A_{i_{1}}, \dots, A_{i_{m}}

(where

m \geq 1

We compute how many times

x

is counted by the right-hand side. For

x

to lie in the intersection

⋂_{i \in S} A_{i}

, every index in

S

must be among

{i_{1}, \dots, i_{m}}

. The number of subsets

S

of size

k

drawn from

{i_{1}, \dots, i_{m}}

(k m)

Thus the total count of

x

on the right-hand side is

k = 1 \sum m (- 1)^{k + 1} (k m) = 1 - k = 0 \sum m (- 1)^{k} (k m) = 1 - (1 - 1)^{m} = 1

where we applied the binomial theorem. Every element of the union is counted exactly once, and the identity follows. □

Remark 3.

The heart of the proof is the identity

(1 - 1)^{m} = 0

for

m \geq 1

. This special case of the binomial theorem is what guarantees the perfect cancellation of all overcounting. It is the engine that makes inclusion–exclusion work.

4 Derangements

Definition 4 (Derangement).

A permutation

σ

{1, 2, \dots, n}

satisfying

σ (i) \neq = i

for every

i

is called a derangement. The number of derangements is denoted

D_{n}

Theorem 5.

D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !} .

Proof.

Let

A_{i} = {σ \in S_{n} ∣ σ (i) = i}

be the set of permutations that fix

i

. Then

D_{n} = n! - ∣ A_{1} \cup A_{2} \cup \dots \cup A_{n} ∣

For any subset

S

of size

k

, the intersection

⋂_{i \in S} A_{i}

consists of all permutations that fix every element of

S

. The remaining

n - k

elements may be permuted freely, so

∣ ⋂_{i \in S} A_{i} ∣ = (n - k)!

By inclusion–exclusion,

∣ A_{1} \cup \dots \cup A_{n} ∣ = k = 1 \sum n (- 1)^{k + 1} (k n) (n - k)!

Therefore,

D_{n} = n! - k = 1 \sum n (- 1)^{k + 1} (k n) (n - k)! = k = 0 \sum n (- 1)^{k} (k n) (n - k)! = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !} .

□

Remark 6.

n

grows,

D_{n} / n!

converges to

1/ e \approx 0.3679

. In other words, the probability that a uniformly random permutation is a derangement is roughly

36.8%

, essentially independent of

n

. This is a beautiful instance of a discrete quantity converging to a value expressed in terms of

e

5 A competitive-programming classic: integers coprime to given primes

Example 7 (Counting integers not divisible by any of

p_{1}, \dots, p_{k}

Let

A_{i} = {m ∣ 1 \leq m \leq n, p_{i} ∣ m}

, so

∣ A_{i} ∣ = ⌊ n / p_{i} ⌋

. If

p_{1}, \dots, p_{k}

are distinct primes, then

∣ ⋂_{i \in S} A_{i} ∣ = ⌊ n / \prod_{i \in S} p_{i} ⌋

By inclusion–exclusion, the number of integers in

{1, \dots, n}

divisible by none of

p_{1}, \dots, p_{k}

n - i = 1 ⋃ k A_{i} = n - k = 1 \sum n (- 1)^{k + 1} ∣ S ∣ = k \sum ⌊ \frac{n}{\prod _{i \in S} p _{i}} ⌋ .

This is also the computation underlying Euler's totient function

φ (n)

Remark 8.

For

k

prime factors, one must enumerate all

2^{k}

subsets. When

k \leq 20

, this amounts to roughly

2^{20} \approx 1 0^{6}

operations – perfectly tractable. For larger values of

k

, alternative approaches are needed.

6 A glimpse of Mobius inversion

Remark 9.

Inclusion–exclusion is, in fact, a special case of the Mobius inversion formula. On a partially ordered set

(P, \leq)

, if functions

f

and

g

satisfy

g (x) = \sum_{y \leq x} f (y)

, then

f

can be recovered via

f (x) = \sum_{y \leq x} μ (x, y) g (y)

, where

μ

is the Mobius function of the poset. On the Boolean lattice (the power set ordered by inclusion), the Mobius function is

μ (S, T) = (- 1)^{∣ S ∖ T ∣}

– and this is precisely the source of the alternating signs in inclusion–exclusion.

7 Takeaway

Inclusion–exclusion ensures that every element is counted exactly once, with the cancellation guaranteed by the binomial identity $(1 - 1)^{m} = 0$ .
Derangements provide a beautiful application: $D_{n} / n! \to 1/ e$ .
In competitive programming, the principle yields a standard method for counting integers satisfying divisibility constraints.
Inclusion–exclusion is a special case of Mobius inversion on partially ordered sets, opening the door to a far more general theory.

In the next article, we explore the idea of encoding a sequence as a function – the generating function – and discover how it transforms recurrences into algebra.

Combinatorics Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 フォロワー·105 記事

Inclusion--exclusion: why the alternating signs work

1 Two sets: the Venn diagram

2 The general formula

3 Proof via indicator functions

4 Derangements

5 A competitive-programming classic: integers coprime to given primes

6 A glimpse of Mobius inversion

7 Takeaway

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry