The Inclusion--Exclusion Principle: Counting by Alternating Sums

We prove the inclusion--exclusion principle and apply it to derive the formula for the number of derangements D_n, Euler's totient function, the relationship between surjections and Stirling numbers of the second kind, and the M\"{o}bius inversion formula.

Folio Official

March 1, 2026

1 The Inclusion–Exclusion Principle

Theorem 1 (Inclusion–exclusion principle).

For finite sets

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

i = 1 ⋃ n A_{i} = k = 1 \sum n (- 1)^{k - 1} 1 \leq i_{1} < \dots < i_{k} \leq n \sum ∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣.

Proof.

We show that each element

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

contributes exactly

1

to the right-hand side. Suppose

x

belongs to exactly

m

of the sets

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

. Its contribution to 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

since

m \geq 1

ensures

(1 - 1)^{m} = 0

. Hence every element is counted exactly once. □

2 Derangements

Definition 2 (Derangement).

A permutation

σ

{1, 2, \dots, n}

satisfying

σ (i) \neq = i

for all

1 \leq i \leq n

is called a derangement. The number of derangements is denoted

D_{n}

Theorem 3.

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

Proof.

Define

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

. Then

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

. Since

∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣ = (n - k)!

, the inclusion–exclusion principle gives

∣ 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 !} .

□

Corollary 4.

D_{n}

is the nearest integer to

n! / e

. That is,

D_{n} = ⌊ n! / e + 1/2 ⌋

3 Euler's Totient Function

Theorem 5.

Let the prime factorization of a positive integer

n

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}

. Then

φ (n) = n i = 1 \prod k (1 - \frac{1}{p _{i}}) .

Proof.

Define

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

. Then

φ (n) = n - ∣ A_{1} \cup \dots \cup A_{k} ∣

. Since

∣ A_{i_{1}} \cap \dots \cap A_{i_{j}} ∣ = n / (p_{i_{1}} \dots p_{i_{j}})

, inclusion–exclusion yields

φ (n) = n - i \sum \frac{n}{p _{i}} + i < j \sum \frac{n}{p _{i} p _{j}} - \dots = n i = 1 \prod k (1 - \frac{1}{p _{i}}) .

□

4 Surjections and Stirling Numbers of the Second Kind

Definition 6 (Stirling number of the second kind).

The number of ways to partition an

n

-element set into

k

nonempty subsets is called a Stirling number of the second kind, denoted

S (n, k)

{\frac{n}{k}}

Theorem 7.

S (n, k) = \frac{1}{k !} j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n}

Proof.

Recall that the number of surjections from an

n

-element set

A

onto a

k

-element set

B

\sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}

(established previously). A surjection

f : A \to B

corresponds to a partition of

A

into

k

blocks together with a labeling of these blocks by the elements of

B

. Since there are

k!

such labelings, we obtain

S (n, k) = (number of surjections) / k!

. □

5 The Möbius Inversion Formula

Definition 8 (M\"obius function).

The Möbius function

μ : Z_{> 0} \to {- 1, 0, 1}

is defined by

μ (n) = ⎩ ⎨ ⎧ 1 (- 1)^{k} 0 n = 1 n = p_{1} p_{2} \dots p_{k} (a product of k distinct primes) otherwise (i.e., n has a squared prime factor)

Theorem 9 (M\"obius inversion formula).

For arithmetic functions

f

and

g

g (n) = d ∣ n \sum f (d) ⟺ f (n) = d ∣ n \sum μ (n / d) g (d) .

Proof.

Substitute

g (d) = \sum_{e ∣ d} f (e)

into the right-hand side:

d ∣ n \sum μ (n / d) e ∣ d \sum f (e) = e ∣ n \sum f (e) d ∣ n e ∣ d \sum μ (n / d) .

Setting

d = e k

, the inner sum becomes

\sum_{k ∣ (n / e)} μ (n / (e k))

. Writing

m = n / e

, this equals

\sum_{l ∣ m} μ (l)

, which is a well-known identity: it equals

1

when

m = 1

and

0

when

m > 1

. Hence the right-hand side reduces to

f (n)

. □

Example 10.

Taking

g (n) = n

(the identity function), the identity

n = \sum_{d ∣ n} φ (d)

holds. By the Mö

φ (n) = \sum_{d ∣ n} μ (n / d) \cdot d

Combinatorics Discrete Mathematics Textbook Inclusion-Exclusion Mobius Inversion

Folio Official

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

1 followers·107 articles

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Folio Official

March 1, 2026

1 The Inclusion–Exclusion Principle

Theorem 1 (Inclusion–exclusion principle).

For finite sets

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

i = 1 ⋃ n A_{i} = k = 1 \sum n (- 1)^{k - 1} 1 \leq i_{1} < \dots < i_{k} \leq n \sum ∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣.

Proof.

We show that each element

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

contributes exactly

1

to the right-hand side. Suppose

x

belongs to exactly

m

of the sets

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

. Its contribution to 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

since

m \geq 1

ensures

(1 - 1)^{m} = 0

. Hence every element is counted exactly once. □

2 Derangements

Definition 2 (Derangement).

A permutation

σ

{1, 2, \dots, n}

satisfying

σ (i) \neq = i

for all

1 \leq i \leq n

is called a derangement. The number of derangements is denoted

D_{n}

Theorem 3.

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

Proof.

Define

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

. Then

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

. Since

∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣ = (n - k)!

, the inclusion–exclusion principle gives

∣ 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 !} .

□

Corollary 4.

D_{n}

is the nearest integer to

n! / e

. That is,

D_{n} = ⌊ n! / e + 1/2 ⌋

3 Euler's Totient Function

Theorem 5.

Let the prime factorization of a positive integer

n

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}

. Then

φ (n) = n i = 1 \prod k (1 - \frac{1}{p _{i}}) .

Proof.

Define

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

. Then

φ (n) = n - ∣ A_{1} \cup \dots \cup A_{k} ∣

. Since

∣ A_{i_{1}} \cap \dots \cap A_{i_{j}} ∣ = n / (p_{i_{1}} \dots p_{i_{j}})

, inclusion–exclusion yields

φ (n) = n - i \sum \frac{n}{p _{i}} + i < j \sum \frac{n}{p _{i} p _{j}} - \dots = n i = 1 \prod k (1 - \frac{1}{p _{i}}) .

□

4 Surjections and Stirling Numbers of the Second Kind

Definition 6 (Stirling number of the second kind).

The number of ways to partition an

n

-element set into

k

nonempty subsets is called a Stirling number of the second kind, denoted

S (n, k)

{\frac{n}{k}}

Theorem 7.

S (n, k) = \frac{1}{k !} j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n}

Proof.

Recall that the number of surjections from an

n

-element set

A

onto a

k

-element set

B

\sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}

(established previously). A surjection

f : A \to B

corresponds to a partition of

A

into

k

blocks together with a labeling of these blocks by the elements of

B

. Since there are

k!

such labelings, we obtain

S (n, k) = (number of surjections) / k!

. □

5 The Möbius Inversion Formula

Definition 8 (M\"obius function).

The Möbius function

μ : Z_{> 0} \to {- 1, 0, 1}

is defined by

μ (n) = ⎩ ⎨ ⎧ 1 (- 1)^{k} 0 n = 1 n = p_{1} p_{2} \dots p_{k} (a product of k distinct primes) otherwise (i.e., n has a squared prime factor)

Theorem 9 (M\"obius inversion formula).

For arithmetic functions

f

and

g

g (n) = d ∣ n \sum f (d) ⟺ f (n) = d ∣ n \sum μ (n / d) g (d) .

Proof.

Substitute

g (d) = \sum_{e ∣ d} f (e)

into the right-hand side:

d ∣ n \sum μ (n / d) e ∣ d \sum f (e) = e ∣ n \sum f (e) d ∣ n e ∣ d \sum μ (n / d) .

Setting

d = e k

, the inner sum becomes

\sum_{k ∣ (n / e)} μ (n / (e k))

. Writing

m = n / e

, this equals

\sum_{l ∣ m} μ (l)

, which is a well-known identity: it equals

1

when

m = 1

and

0

when

m > 1

. Hence the right-hand side reduces to

f (n)

. □

Example 10.

Taking

g (n) = n

(the identity function), the identity

n = \sum_{d ∣ n} φ (d)

holds. By the Mö

φ (n) = \sum_{d ∣ n} μ (n / d) \cdot d

Combinatorics Discrete Mathematics Textbook Inclusion-Exclusion Mobius Inversion

Folio Official

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

1 followers·107 articles

The Inclusion--Exclusion Principle: Counting by Alternating Sums

1 The Inclusion–Exclusion Principle

2 Derangements

3 Euler's Totient Function

4 Surjections and Stirling Numbers of the Second Kind

5 The Möbius Inversion Formula

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

Combinatorial Designs and Latin Squares: Balanced Arrangements

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

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs

The Inclusion--Exclusion Principle: Counting by Alternating Sums

1 The Inclusion–Exclusion Principle

2 Derangements

3 Euler's Totient Function

4 Surjections and Stirling Numbers of the Second Kind

5 The Möbius Inversion Formula

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

Combinatorial Designs and Latin Squares: Balanced Arrangements

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

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs