한
|A∪B∪C|
Set theory · Concept hub

Inclusion-Exclusion Principle

1854 CE19th-century Britain (Sylvester)

Departure question

Find order without counting everythingPort 5 of 16

“Through Inclusion-Exclusion Principle: How can we find hidden order without counting everything?”

Trace recurring structure through exploding possibilities, divisibility, and the apparent irregularity of primes.

An editorial avatar of Erdős preserving his winged white hair, oversized dark glasses, and red graph threads joining many hands

Continue this question through a person

Paul Erdős

This voyage is an editorial path for understanding, not a claim of direct historical influence or sole invention.

Understand it in one breath

Subtract what you double-counted. When students join multiple clubs, this is how you count each person once. The fact that the probability of a derangement (everyone gets a gift that isn't theirs) is 1/e ≈ 36.8% comes directly from this principle.

At a glance

Random gift exchange among k people

Probability that nobody receives their own gift

n = 2

1/2 = 0.5

n = 3

2/6 ≈ 0.333

n = 4

9/24 = 0.375

n = 5

44/120 ≈ 0.367

n = 10

1334961/10! ≈ 0.3679

n → ∞

1/e ≈ 0.36788

The inclusion–exclusion principle produces the alternating sum ∑(−1)ᵏ/k!. Because it is part of the Taylor expansion of e, it converges to 1/e. A simple counting principle summons e.

Concept

Generalization of |A∪B| = |A|+|B|−|A∩B|. Counting unions by alternating sums of intersections — the workhorse of combinatorics.

Key formula

∣⋃iAi∣=∑i∣Ai∣−∑i<j∣Ai∩Aj∣+⋯\Big|\bigcup_{i} A_i\Big| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \cdots

|∪Aᵢ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − ⋯

Modern applications

Probability and expectation calculations, database UNION queries, and counting derangements and other overlapping cases.

Beyond MathVoyage

Curated sources and problems. Bring one discovery back from OEIS, Project Euler, MathOverflow, or arXiv.

No concept belongs to one person

Follow people who played different roles

These are not inventor credits. They are different ports: opening a problem, sharpening a language, or carrying it into another world.

An editorial avatar of Erdős preserving his winged white hair, oversized dark glasses, and red graph threads joining many hands
Primary next port

Paul Erdős

Open this person’s scenes

Number lenses

A concept looks different when its world of numbers changes

These numbers are editorial lenses for the voyage, not required prerequisites.

ℕ

Natural Numbers

Trace recurring structure through exploding possibilities, divisibility, and the apparent irregularity of primes.

Open the number voyage

ℤ

Integers

Trace recurring structure through exploding possibilities, divisibility, and the apparent irregularity of primes.

Open the number voyage

ℚ

Rational Numbers

Trace recurring structure through exploding possibilities, divisibility, and the apparent irregularity of primes.

Open the number voyage

Concept genealogy

What supports it, and what does it open?

Concepts arriving from before

Combinatorics

Current port

Inclusion-Exclusion Principle

Concepts opened from here

No direct successor port is curated yet.

Only direct editorial links are shown; this is not a complete learning order or historical influence line.