Inclusion-Exclusion Principle

One-line statement: The size of a union of finite sets equals the alternating sum of the sizes of all possible intersections of those sets. Key result in words: Add the sizes of individual sets, subtract pairwise overlaps, add back triple overlaps, and so on, alternating signs, to count a union without double-counting. Where it applies: Combinatorics, probability, number theory (the Euler Totient Function and Sieve Methods), and counting problems with overlapping conditions. Who/when: Formalized by Abraham de Moivre (1718) and named after work by J. J. Sylvester and Henri Poincaré in the 19th century.

The inclusion–exclusion principle is a counting technique that computes the cardinality of a union of finite sets by alternately adding and subtracting the cardinalities of their intersections. In its simplest form, $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ , it corrects the naive overcount that occurs when overlapping elements are counted more than once. The principle generalizes to any finite number of sets and underlies a vast range of combinatorial identities, including the counting of derangements, surjections, and integers coprime to a given number. A surprising fact is that the same alternating-sum structure appears in probability (the formula for the probability of a union of events), in the Euler characteristic of topology, and in the Möbius inversion formula over the Boolean lattice — all manifestations of a single algebraic skeleton.

The Core Insight

When you count elements belonging to at least one of several sets, an element lying in $k$ of them is counted $k$ times if you simply add the individual set sizes. The fix is systematic correction by overlaps: subtract every pairwise intersection, which over-corrects elements in three or more sets, then add back triple intersections, and continue. The miracle is that the coefficients work out so that an element in exactly $k$ sets is counted with net multiplicity $(1 k) - (2 k) + (3 k) - \dots = 1$ , regardless of $k \geq 1$ . The entire principle is the combinatorial identity $\sum_{j = 1}^{k} (- 1)^{j - 1} (j k) = 1$ in disguise.

Formal Statement

Setup and Notation

Let $A_{1}, A_{2}, \dots, A_{n}$ be finite sets. For a nonempty subset $S \subseteq {1, 2, \dots, n}$ of indices, write

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

⟳

A_{S}

is the set of elements common to all sets whose indices appear in

S

; by convention

A_{\emptyset}

is the universal set

U

The quantity $∣ A_{S} ∣$ depends only on which sets are intersected, and the principle expresses $∣ A_{1} \cup \dots \cup A_{n} ∣$ in terms of all these intersection sizes.

Inclusion–Exclusion Principle (Union Form)

For finite sets $A_{1}, \dots, A_{n}$ ,

i = 1 ⋃ n A_{i} = \emptyset \neq = S \subseteq {1, \dots, n} \sum (- 1)^{∣ S ∣ - 1} i \in S ⋂ A_{i}

⟳group terms by the size

k = ∣ S ∣

of the index subset; each size contributes a sum over all

(k n)

intersections of

k

sets, with sign

(- 1)^{k - 1}

Equivalently, expanding by intersection size:

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

⟳this is [2] with the index subsets

S

sorted by their cardinality

k

; inner sum ranges over strictly increasing index tuples.

The first few terms read $S_{1} - S_{2} + S_{3} - \dots$ , where $S_{k}$ is the sum of all $k$ -fold intersection sizes.

Complementary Form

Equivalently, counting elements in none of the sets within a universe $U$ of size $N$ :

U ∖ i = 1 ⋃ n A_{i} = S \subseteq {1, \dots, n} \sum (- 1)^{∣ S ∣} i \in S ⋂ A_{i} = N - S_{1} + S_{2} - \dots

⟳subtract equation [2] from

N = ∣ U ∣

and absorb the

N

term as the

S = \emptyset

contribution where

A_{\emptyset} = U

contributes

+ N

This form is the one used in sieve arguments: $A_{i}$ encodes "having property $i$ ," and the left side counts objects with no listed property.

Why It Holds / Derivation

Indicator-Function / Element-Counting Proof

We prove equation [2] by showing each element of the union contributes exactly $1$ to both sides.

Step 1 — Fix an element. Let

x \in ⋃_{i} A_{i}

, and let

k \geq 1

be the number of sets

A_{i}

containing

x

. The left side of [2] counts

x

exactly once. Step 2 — Count $x$ 's contributions on the right. An intersection

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

contains

x

if and only if

S

is a subset of the

k

indices whose sets contain

x

. The number of such index sets

S

of size

j

(j k)

. Step 3 — Sum the signed contributions. Element

x

contributes to the right side

j = 1 \sum k (- 1)^{j - 1} (j k)

⟳each

S \subseteq

(sets containing

x

) of size

j

adds

(- 1)^{j - 1}

; there are

(j k)

of them.

Step 4 — Evaluate via the binomial theorem. Since

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

for

k \geq 1

, we isolate the

j = 0

term:

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

⟳factor out the sign and use that the full alternating binomial sum vanishes; the missing

j = 0

term equals

1

Step 5 — Conclude. Each

x

in the union contributes exactly

1

to both sides, so the totals are equal. Elements outside the union contribute

0

to both sides.

■

Inductive Proof

Base case

n = 2

∣ A_{1} \cup A_{2} ∣ = ∣ A_{1} ∣ + ∣ A_{2} ∣ - ∣ A_{1} \cap A_{2} ∣

, since elements in the overlap are added twice and removed once. Inductive step. Assume [2] holds for

n - 1

sets. Write

B = A_{1} \cup \dots \cup A_{n - 1}

. Then

∣ B \cup A_{n} ∣ = ∣ B ∣ + ∣ A_{n} ∣ - ∣ B \cap A_{n} ∣

⟳apply the two-set rule with

B

as the first set.

Now $B \cap A_{n} = ⋃_{i = 1}^{n - 1} (A_{i} \cap A_{n})$ , so apply the inductive hypothesis to both $∣ B ∣$ and $∣ B \cap A_{n} ∣$ ; collecting terms reproduces [2] for $n$ sets, with each $k$ -fold intersection appearing exactly once with the correct sign. $■$

Abraham de Moivre | 1667–1754

A French-born Huguenot mathematician who fled to England after the revocation of the Edict of Nantes, de Moivre worked largely as a private tutor and consultant on games of chance. In his 1718 The Doctrine of Chances, he gave an early systematic treatment of the inclusion–exclusion formula in the context of probability problems — notably the "problème des rencontres" (the matching/derangement problem). His work tied the combinatorial identity to practical questions of dice, lotteries, and annuities. The principle's later refinement and naming owe much to J. J. Sylvester and Henri Poincaré, but de Moivre's recognition that overcounting must be corrected by alternating subtraction is the historical seed.

Building Intuition

Imagine three overlapping circular spotlights on a stage, lighting up actors. If you ask each operator "how many actors does your beam touch?" and add the three numbers, an actor standing where two beams overlap gets counted twice, and one in the central three-way overlap gets counted three times. To find how many actors are lit at all, you subtract the pairwise-overlap counts — but this removes the central actor one time too many (counted $3$ , subtracted $3$ , leaving $0$ ). So you add back the triple overlap, restoring her to a single count. The alternating add/subtract pattern is precisely the bookkeeping needed so every lit actor ends up counted exactly once, no matter how many beams reach her.

Three-set inclusion–exclusion: the alternating correction of overlaps

Worked Examples

Counting integers divisible by 2, 3, or 5 up to 100

Given: Count integers

n

with

1 \leq n \leq 100

divisible by

2

3

, or

5

Let $A$ = multiples of 2, $B$ = multiples of 3, $C$ = multiples of 5, within $U = {1, \dots, 100}$ .

Step 1 — Single counts ( $S_{1}$ ):

∣ A ∣ = ⌊ 100/2 ⌋ = 50

∣ B ∣ = ⌊ 100/3 ⌋ = 33

∣ C ∣ = ⌊ 100/5 ⌋ = 20

. So

S_{1} = 50 + 33 + 20 = 103

. Step 2 — Pairwise counts ( $S_{2}$ ):

∣ A \cap B ∣ = ⌊ 100/6 ⌋ = 16

∣ A \cap C ∣ = ⌊ 100/10 ⌋ = 10

∣ B \cap C ∣ = ⌊ 100/15 ⌋ = 6

. So

S_{2} = 16 + 10 + 6 = 32

. Step 3 — Triple count ( $S_{3}$ ):

∣ A \cap B \cap C ∣ = ⌊ 100/30 ⌋ = 3

. Step 4 — Apply [3]:

∣ A \cup B \cup C ∣ = S_{1} - S_{2} + S_{3} = 103 - 32 + 3 = 74

74 integers

(As a check, the number coprime to 30 in this range, via [4], is $100 - 74 = 26$ .)

The derangement problem $D_n$ for $n = 4$

Given: Count permutations of

{1, 2, 3, 4}

with no fixed point (no element maps to itself) — these are derangements.

Let $A_{i}$ = permutations fixing position $i$ . We want permutations in none of the $A_{i}$ , so use complementary form [4] with $N = 4! = 24$ .

Step 1 — Intersection sizes. A permutation fixing a chosen set of

k

positions permutes the remaining

4 - k

freely, giving

(4 - k)!

permutations. There are

(k 4)

ways to choose which

k

positions are fixed. Step 2 — Build the alternating sum (from [4]):

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

Step 3 — Evaluate term by term:

$k = 0$ : $(0 4) 4! = 24$
$k = 1$ : $- (1 4) 3! = - 4 \cdot 6 = - 24$
$k = 2$ : $+ (2 4) 2! = 6 \cdot 2 = 12$
$k = 3$ : $- (3 4) 1! = - 4$
$k = 4$ : $+ (4 4) 0! = 1$

Step 4 — Sum:

24 - 24 + 12 - 4 + 1 = 9

D_{4} = 9 derangements

This matches the closed form $D_{n} = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}$ , giving $D_{4} = 24 (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}) = 9$ .

Common Misconceptions

Signs and stopping points

Three frequent errors:

Forgetting to add back the triple overlap. Subtracting all pairwise intersections over-removes elements in three or more sets; the principle is not "add singles, subtract pairs" — it continues with alternating signs all the way to the $n$ -fold intersection.
Mixing up $(- 1)^{∣ S ∣ - 1}$ (union form [2]) with $(- 1)^{∣ S ∣}$ (complement form [4]). The sign on the leading single-set term is $+$ for the union but the $N$ term carries no negative in the complement form.
Assuming intersection sizes are products. $∣ A \cap B ∣ = ∣ A ∣ \cdot ∣ B ∣$ is false in general for cardinalities; it holds for probabilities only under independence. For counting, you must determine each intersection size directly.

Naive subtraction fails for three or more sets

Take $A = B = C = {x}$ , a single shared element. Then $∣ A \cup B \cup C ∣ = 1$ .

If you (incorrectly) used only "singles minus pairs":

S_{1} - S_{2} = (1 + 1 + 1) - (1 + 1 + 1) = 0 \neq = 1.

The element

x

, counted

3

times then subtracted

3

times, vanishes. Only by adding back

S_{3} = ∣ A \cap B \cap C ∣ = 1

do we recover the correct

3 - 3 + 1 = 1

. This shows the full alternating sum is essential — truncating it gives the wrong answer.

Connections

Inclusion–exclusion is a special case of Möbius inversion on the Boolean lattice of subsets, where the alternating signs $(- 1)^{∣ S ∣}$ are exactly the Möbius function values; see Mobius Inversion Formula. In probability it becomes the formula $P (⋃ A_{i}) = \sum P (A_{i}) - \sum P (A_{i} \cap A_{j}) + \dots$ , foundational in Probability Theory. Its number-theoretic incarnation is the Sieve of Eratosthenes and the formula for the Euler Totient Function $φ (n) = n \prod_{p ∣ n} (1 - 1/ p)$ . The Bonferroni inequalities arise from truncating the alternating sum, giving alternating upper and lower bounds. Topologically, the same alternating structure governs the additivity of the Euler Characteristic under unions of cells.

Real-World Applications

Sieve of Eratosthenes & prime counting — estimating how many integers up to $x$ survive removal of all multiples of small primes uses [4] directly; this is the root of analytic Sieve Methods.
Euler's totient function — counting integers coprime to $n$ applies inclusion–exclusion over the distinct prime divisors of $n$ .
Network reliability — computing the probability that at least one of several redundant paths in a communications network functions, where paths share components (events are not independent).
Database query optimization — estimating the number of records satisfying "at least one of several filter conditions" requires correcting for records matching multiple conditions.
Cryptographic collision counting — bounding the number of hash inputs colliding on at least one of several outputs.
Surjection and onto-map enumeration — counting functions from an $m$ -set onto an $n$ -set (used in occupancy/balls-in-boxes problems and Stirling numbers) is a direct inclusion–exclusion over "missed targets."
Coupon collector and matching problems — derangement-based scenarios such as the hat-check problem and probability of a perfect mismatch in secret-Santa assignments.

Historical Development

1718 — Abraham de Moivre, in The Doctrine of Chances, treats the matching problem (rencontres) using alternating-sum corrections, an early probabilistic inclusion–exclusion.
1779 — Leonhard Euler develops the totient function and uses product-over-primes reasoning equivalent to inclusion–exclusion.
1854 — Daniel da Silva states a general form of the principle in a Portuguese memoir, sometimes giving the result the name "da Silva's formula."
1867 — J. J. Sylvester independently formulates and applies the principle in combinatorics; the name "Sylvester's sieve" is sometimes used.
1883 — H. Poincaré states the probabilistic union formula in his work on probability, lending it the alternative name "Poincaré's formula."
1936 — C. E. Bonferroni publishes the inequalities obtained by truncating the alternating series, central to multiple-comparison statistics.
1964 — Gian-Carlo Rota, in On the Foundations of Combinatorial Theory I, unifies inclusion–exclusion as Möbius inversion over partially ordered sets, revealing its deep algebraic structure.
20th c. onward — The principle becomes standard in textbooks of enumerative combinatorics (Riordan, Stanley) and a workhorse of analytic number theory's sieve methods (Brun, Selberg).

Subtleties & Limits

Inclusion–exclusion is exact for finitely many sets, but practically it can require summing $2^{n} - 1$ terms, which is computationally infeasible for large $n$ — exact application is #P-hard for general systems (e.g., reliability polynomials). This motivates sieve theory's central tension: how to extract good bounds from truncated or weighted versions of the alternating sum. The Bonferroni inequalities give crude bounds; the deeper achievements of Brun's sieve, the Selberg sieve, and the large sieve replace the rigid signs of pure inclusion–exclusion with optimized weights to tame error terms. The famous "parity problem" of sieve theory — the inability of classical sieves to distinguish numbers with an even versus odd number of prime factors — is fundamentally a limitation on how much the inclusion–exclusion structure can detect, and remains a guiding obstacle in attacks on problems like the twin prime conjecture and Goldbach's conjecture.