Inclusion-Exclusion Principle

⚡ Key Takeaways

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 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 $\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots = 1$ , regardless of $k \ge 1$ . The entire principle is the combinatorial identity $\sum_{j=1}^{k}(-1)^{j-1}\binom{k}{j} = 1$ in disguise.

DefinitionSetup 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

1

\quad A_S = \bigcap_{i \in S} A_i

Derivation hint: $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 \cdots \cup A_n|$ in terms of all these intersection sizes.

TheoremInclusion–Exclusion Principle (Union Form)

For finite sets $A_1, \dots, A_n$ ,

2

\quad \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset \ne S \subseteq \{1,\dots,n\}} (-1)^{|S|-1} \left| \bigcap_{i \in S} A_i \right|

Derivation hint: group terms by the size $k = |S|$ of the index subset; each size contributes a sum over all $\binom{n}{k}$ intersections of $k$ sets, with sign $(-1)^{k-1}$ . Equivalently, expanding by intersection size:

3

\quad \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{1 \le i_1 < \cdots < i_k \le n} \left| A_{i_1} \cap \cdots \cap A_{i_k} \right|

Derivation hint: 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 - \cdots$ , where $S_k$ is the sum of all $k$ -fold intersection sizes.

TheoremComplementary Form

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

4

\quad \left| U \setminus \bigcup_{i=1}^{n} A_i \right| = \sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} \left| \bigcap_{i \in S} A_i \right| = N - S_1 + S_2 - \cdots

Derivation hint: 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.

ProofIndicator-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 \bigcup_i A_i$ , and let $k \ge 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 $\bigcap_{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$ is $\binom{k}{j}$ .

Step 3 — Sum the signed contributions. Element $x$ contributes to the right side

5

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

Derivation hint: each $S \subseteq$ (sets containing $x$ ) of size $j$ adds $(-1)^{j-1}$ ; there are $\binom{k}{j}$ of them.

Step 4 — Evaluate via the binomial theorem. Since $\sum_{j=0}^{k}(-1)^j \binom{k}{j} = (1-1)^k = 0$ for $k \ge 1$ , we isolate the $j=0$ term:

6

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

Derivation hint: 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. $\blacksquare$

∎

ProofInductive 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 \cdots \cup A_{n-1}$ . Then

7

\quad |B \cup A_n| = |B| + |A_n| - |B \cap A_n|

Derivation hint: apply the two-set rule with $B$ as the first set. Now $B \cap A_n = \bigcup_{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. $\blacksquare$

∎

mathematician · 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.

🧠 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.

Figure

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

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

Given: Count integers $n$ with $1 \le n \le 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| = \lfloor 100/2 \rfloor = 50$ , $|B| = \lfloor 100/3 \rfloor = 33$ , $|C| = \lfloor 100/5 \rfloor = 20$ . So $S_1 = 50 + 33 + 20 = 103$ .

Step 3 — Triple count ( $S_3$ ): $|A \cap B \cap C| = \lfloor 100/30 \rfloor = 3$ .

Step 4 — Apply [3]: $|A \cup B \cup C| = S_1 - S_2 + S_3 = 103 - 32 + 3 = 74$ .

\boxed{74 \text{ integers}}

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

ExampleThe 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 $\binom{4}{k}$ ways to choose which $k$ positions are fixed.

Step 2 — Build the alternating sum (from [4]):

D_4 = \sum_{k=0}^{4} (-1)^k \binom{4}{k}(4-k)!

Step 3 — Evaluate term by term:

$k=0$ : $\binom{4}{0}\,4! = 24$
$k=1$ : $-\binom{4}{1}\,3! = -4 \cdot 6 = -24$
$k=2$ : $+\binom{4}{2}\,2! = 6 \cdot 2 = 12$
$k=3$ : $-\binom{4}{3}\,1! = -4$
$k=4$ : $+\binom{4}{4}\,0! = 1$

Step 4 — Sum: $24 - 24 + 12 - 4 + 1 = 9$ .

\boxed{D_4 = 9 \text{ derangements}}

This matches the closed form $D_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!}$ , giving $D_4 = 24(1 - 1 + \tfrac12 - \tfrac16 + \tfrac1{24}) = 9$ .

⚠️ Signs and stopping points

Three frequent errors: 1. 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. 2. 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. 3. 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.

CounterexampleNaive 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 \ne 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.

connection

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(\bigcup A_i) = \sum P(A_i) - \sum P(A_i \cap A_j) + \cdots$ , foundational in Probability Theory. Its number-theoretic incarnation is the Sieve of Eratosthenes and the formula for the Euler Totient Function $\varphi(n) = n\prod_{p\mid 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.

🔬 Where this appears

⏳ History

- 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).

open-problem

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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also