The Principle of Inclusion-Exclusion

How many integers from $1$ to $1000$ are divisible by $3$ , $5$ , or $7$ ? Naively adding the three counts overcounts numbers divisible by more than one of these. So we must correct for the overcounting — and then correct the correction. This simple tension between the Sum and Product Rules and overlapping sets is the seed of one of the most versatile counting tools in combinatorics: the Principle of Inclusion-Exclusion (PIE). PIE matters because most interesting counting problems are not about disjoint collections. Instead they involve unions and complements of overlapping conditions — numbers avoiding certain divisors, functions missing certain outputs, permutations avoiding certain fixed points, arrangements violating certain adjacency constraints. Whenever a problem can be phrased as "count the elements satisfying at least one of several properties," PIE helps. The same holds dually for "count the elements satisfying none." PIE turns that question into a computable alternating sum over intersections. Each of these is often far easier to count than the union directly. The big picture is that a finite set can be built from overlapping subsets. Their interactions form a Boolean lattice. PIE is precisely the Möbius-function calculation on that lattice, made elementary through a counting argument. It generalizes the humble observation that $|A \cup B| = |A| + |B| - |A \cap B|$ to arbitrarily many sets. As intersections deepen, the signs alternate between $+$ and $-$ . This article develops PIE rigorously from the two-set and three-set cases up to the full $n$ -set alternating-sum theorem. It proves the theorem two independent ways, and works through asymmetric numeric examples. It also sets up the machinery — counting elements satisfying none of several properties. This machinery powers the classical theory of Derangements, the counting of surjective functions, and enumeration of restricted Integer Partitions.

Key takeaways

PIE computes $|A_1 \cup \cdots \cup A_n|$ as an alternating sum of sizes of all possible intersections of the sets.
The two-set case $|A\cup B|=|A|+|B|-|A\cap B|$ is the seed; three-set and $n$ -set versions add correction terms recursively.
The complementary form counts elements satisfying none of $n$ properties, which is the engine behind derangements and surjection counts.
The proof works by tracking, for each element, how many times it is counted at each stage — this reduces to a binomial identity.
PIE is a special case of Möbius inversion on the subset lattice, though it can be proved without that machinery.
Key idea: overcounting from overlaps is corrected by alternating $+/-$ terms indexed by the sizes of all subset intersections.

Where this lives today

Inclusion-exclusion is a working tool across mathematics and its applications. In enumerative combinatorics it underlies the count of Derangements (permutations with no fixed point), the formula for Counting Surjections used above, and the enumeration of integer solutions to equations under upper-bound constraints — a technique feeding directly into Integer Partitions with bounded part sizes. In elementary number theory, PIE proves the formula for Euler's totient function $\varphi(n)$ by excluding multiples of each prime factor of $n$ , and computes counts of integers free of specified divisors, exactly as in the worked example above. In probability theory, the same alternating sum (applied to probabilities instead of cardinalities) gives Bonferroni's inequalities, used to bound event probabilities when full inclusion-exclusion is computationally infeasible. In graph theory and algorithms, PIE underlies the chromatic polynomial computation via the deletion–contraction-adjacent "broken circuit" methods and dynamic-programming algorithms (such as the Held–Karp-style inclusion-exclusion algorithms for Hamiltonian cycles and graph coloring) achieving $O(2^n \mathrm{poly}(n))$ running time. In cryptography and coding theory, sieve methods analogous to PIE estimate collision probabilities and counts of "bad" keys avoiding structural weaknesses. In statistical mechanics and combinatorial physics, inclusion-exclusion sums appear in cluster expansions and in computing partition-function corrections for interacting systems on lattices.

Ask the tutor: How does inclusion-exclusion combine with the Product Rule to count permutations avoiding several forbidden positions at once, as in the derangement problem?

U

Intuition

Picture three overlapping disks representing $A_1, A_2, A_3$ . If you simply add $|A_1|+|A_2|+|A_3|$ , every point lying in exactly two disks gets counted twice, and every point lying in all three gets counted three times. Subtracting all pairwise intersections $|A_1\cap A_2| + |A_1\cap A_3| + |A_2\cap A_3|$ fixes the doubly-counted points, but it removes the triply-counted point three times (once per pair), on top of having added it three times originally — net effect zero, when it should count once. Adding back $|A_1\cap A_2\cap A_3|$ restores exactly one count for that region. This alternating add/subtract/add pattern is the whole idea; the theorem below shows it persists for any number of sets, and the proof shows why the arithmetic always lands on exactly $1$ for every element of the union.

Figure

Venn diagram bookkeeping for three sets: each region's net multiplicity after inclusion-exclusion is exactly 1

Theorem statement and proof

n

m \ge 1

(1-1)^m

\bigcup_{i=1}^n A_i

U

\left|U \setminus \bigcup A_i\right| = |U| - \left|\bigcup A_i\right|

Worked examples

Example 1 (asymmetric divisibility count). How many integers in $\{1, 2, \dots, 2000\}$ are divisible by $6$ , by $10$ , or by $15$ ? Let $U = \{1,\dots,2000\}$ , and let $A_1, A_2, A_3$ be the multiples of $6, 10, 15$ respectively within $U$ . For any $d$ , the number of multiples of $d$ in $U$ is $\lfloor 2000/d \rfloor$ . Singles:

|A_1| = \lfloor 2000/6\rfloor = 333, \quad |A_2| = \lfloor 2000/10\rfloor = 200, \quad |A_3| = \lfloor 2000/15\rfloor = 133.

Pairwise intersections use least common multiples: $\mathrm{lcm}(6,10)=30$ , $\mathrm{lcm}(6,15)=30$ , $\mathrm{lcm}(10,15)=30$ .

|A_1\cap A_2| = \lfloor 2000/30\rfloor = 66, \quad |A_1\cap A_3| = 66, \quad |A_2\cap A_3| = 66.

Triple intersection: $\mathrm{lcm}(6,10,15) = 30$ , so

|A_1\cap A_2\cap A_3| = \lfloor 2000/30 \rfloor = 66.

By the theorem,

|A_1\cup A_2\cup A_3| = (333+200+133) - (66+66+66) + 66 = 666 - 198 + 66 = 534.

So exactly $534$ integers from $1$ to $2000$ are divisible by $6$ , $10$ , or $15$ . (Sanity check: since $\mathrm{lcm}(6,10,15)=30$ and all pairwise lcms also equal $30$ , actually $A_1\cap A_2 = A_1\cap A_3 = A_2 \cap A_3 = A_1\cap A_2\cap A_3$ exactly — every number divisible by any two of $6,10,15$ is automatically divisible by $30$ and hence by all three. This is a genuine, slightly surprising numerical coincidence of this example, not a hidden symmetry of the method: it happens because $6=2\cdot3$ , $10=2\cdot5$ , $15=3\cdot5$ pairwise "cover" all three primes $2,3,5$ .)

Example 2 (counting onto functions — foreshadowing surjections). How many functions $f : \{1,2,3,4,5\} \to \{a,b,c\}$ are surjective (i.e., hit every element of the codomain)? Let $U$ be the set of all functions from a $5$ -element domain to a $3$ -element codomain, so $|U| = 3^5 = 243$ by the Product Rule. For $i \in \{a,b,c\}$ , let $A_i$ be the set of functions that miss the value $i$ (i.e. $i$ is not in the image). A function is surjective exactly when it lies in none of $A_a, A_b, A_c$ — so the complementary form of PIE applies directly. A function missing a specific set $I \subseteq \{a,b,c\}$ of values is the same as a function from a $5$ -element set into the remaining $3-|I|$ values, and there are $(3-|I|)^5$ such functions by the Product Rule; this quantity depends only on $|I|$ , so

|A_I| = (3-|I|)^5.

Applying the corollary with $n=3$ properties (missing $a$ , missing $b$ , missing $c$ ):

\#\{\text{surjections}\} = \sum_{I \subseteq \{a,b,c\}} (-1)^{|I|} (3-|I|)^5 = \sum_{k=0}^{3} (-1)^k \binom{3}{k} (3-k)^5.

Compute term by term:

$k=0$ : $\binom{3}{0}(3)^5 = 1 \cdot 243 = 243$ .
$k=1$ : $-\binom{3}{1}(2)^5 = -3\cdot 32 = -96$ .
$k=2$ : $\binom{3}{2}(1)^5 = 3 \cdot 1 = 3$ .
$k=3$ : $-\binom{3}{3}(0)^5 = -1\cdot 0 = 0$ .

Sum: $243 - 96 + 3 - 0 = 150$ . So there are exactly $150$ surjective functions from a $5$ -element set onto a $3$ -element set. (This matches the general surjection-count formula that PIE produces for Counting Surjections in general: $\sum_{k=0}^{m}(-1)^k\binom{m}{k}(m-k)^n$ surjections from an $n$ -set onto an $m$ -set — here $m=3$ , $n=5$ .)

A_1,\dots,A_n

Scope, edge cases & common traps

Situation	What happens
$n=2$ sets	Reduces to $\|A\cup B\| = \|A\|+\|B\|-\|A\cap B\|$ , the classical two-set case.
Some $A_i$ pairwise disjoint	All higher intersections vanish; PIE reduces to the plain Sum and Product Rules additive count.
All $A_i$ equal	Formula still holds but is wasteful; direct reasoning is simpler.
Infinite index set $n=\infty$	Theorem as stated does not apply; requires measure-theoretic or probabilistic analogues (Bonferroni-type inequalities), beyond this scope.
Complementary form	Requires an ambient finite universe $U$ containing all $A_i$ ; without it "none of the properties" is undefined.

The mathematician behind it

Origins · 1 minAbraham de Moivre and how this was discovered

Abraham de Moivre

1667–1754 · early probability and combinatorics in England

De Moivre, a French Huguenot mathematician who emigrated to England after the revocation of the Edict of Nantes, developed early inclusion-exclusion-type arguments in his work on probability, particularly in The Doctrine of Chances (1718), where he analyzed the probability that at least one of several events occurs. The systematic algebraic formulation of the principle for arbitrarily many sets — with the modern alternating-sum notation — was consolidated over the following two centuries, with contributions from Daniel da Silva, J. J. Sylvester, and Henri Poincaré, and is sometimes called Da Silva's formula or the Sylvester–Poincaré formula in older European texts.

History

- 1708 — De Moivre begins publishing work on games of chance involving compound event probabilities.

- 1718 — The Doctrine of Chances appears, containing early sieve-type arguments for "at least one" events.

- 1854 — Daniel da Silva publishes a rigorous general statement of the sieve formula for finite sets.

- 1883 — J. J. Sylvester writes on the combinatorial "method of exclusion" in the modern algebraic style.

- 1896 — Henri Poincaré applies inclusion-exclusion reasoning within a general combinatorial and probabilistic framework.

Is inclusion-exclusion only for two or three sets, or does it really work for any number

n

It works for any finite $n \ge 1$ . The two- and three-set cases are just small instances of the same general alternating-sum formula proved above. For general $n$ , the formula sums over all $2^n - 1$ nonempty subsets of indices, with the sign of each term determined solely by the size of that subset: odd-sized index sets get a $+$ sign, even-sized get a $-$ sign. The proof by double counting (tracking how many times a fixed element is counted) works uniformly in $n$ , using the binomial identity $\sum_{k=0}^m (-1)^k \binom{m}{k}=0$ , which holds for every $m \ge 1$ regardless of how large $n$ is.

How is this related to the Möbius function or Möbius inversion?

Inclusion-exclusion is exactly Möbius inversion on the lattice of subsets of $\{1,\dots,n\}$ , ordered by inclusion. The Möbius function of this lattice is $\mu(I,J) = (-1)^{|J|-|I|}$ for $I \subseteq J$ , and the general Möbius inversion formula, when specialized to this lattice and to the function $I \mapsto |A_I|$ , produces precisely the alternating-sum formula proved here. The combinatorial proof given in this article, however, is self-contained and does not require developing the general theory of Möbius functions on posets — it only needs elementary counting and one binomial identity.

Can PIE be used to compute probabilities instead of counts?

Yes. If $A_1,\dots,A_n$ are events in a finite (or more generally discrete) probability space, dividing every term in the theorem by the size of the sample space (or working directly with probability measure instead of counting measure) gives

P\Bigl(\bigcup_{i=1}^n A_i\Bigr) = \sum_{k=1}^n (-1)^{k+1}\sum_{i_1<\cdots<i_k} P(A_{i_1}\cap\cdots\cap A_{i_k}).

This is the standard probabilistic form of inclusion-exclusion, and truncating the alternating sum after $k$ terms gives the Bonferroni inequalities, useful upper and lower bounds when computing every intersection probability is impractical.

Why does the complementary "none of the properties" form include an

I = \varnothing

term equal to

|U|

The empty intersection over zero sets is conventionally defined to be the entire universe $U$ (the intersection of no constraints excludes nothing), so $A_\varnothing := U$ by convention. This convention makes the corollary's formula uniform: summing $(-1)^{|I|}|A_I|$ over all subsets $I$ , including the empty one, automatically starts from $|U|$ and then subtracts, adds back, and so on — exactly matching $|U| - |\bigcup A_i|$ once you expand the union formula from the main theorem and combine terms.

What is the connection between PIE and counting derangements?

A derangement of $\{1,\dots,n\}$ is a permutation with no fixed point. Let $U$ be the set of all $n!$ permutations, and let $A_i$ be the set of permutations fixing position $i$ (so $|A_i| = (n-1)!$ , and more generally $|A_I| = (n-|I|)!$ for $|I|$ fixed positions). Derangements are exactly the permutations in none of the $A_i$ , so the complementary form of PIE gives the derangement count $D_n = \sum_{k=0}^n (-1)^k \binom{n}{k}(n-k)!= n!\sum_{k=0}^n \frac{(-1)^k}{k!}$ , the classical formula developed fully under Derangements.

Does the order in which the sets

A_1,\dots,A_n

are listed affect the formula?

No. The formula sums over all subsets $I$ of the index set $\{1,\dots,n\}$ , and set intersection is commutative and associative, so $A_I = \bigcap_{i\in I} A_i$ does not depend on any ordering of the elements of $I$ . Relabeling or reordering the sets $A_1,\dots,A_n$ permutes the terms of the sum but does not change its value, since addition is also commutative. The formula is intrinsically defined in terms of the sets themselves, not any sequence in which they are presented.

Is there a version of PIE for more than two "overlapping conditions" phrased without sets, e.g. directly with logical predicates?

Yes — PIE is often stated for a finite set $U$ together with $n$ properties $P_1,\dots,P_n$ that elements of $U$ may or may not satisfy. Letting $A_i = \{x \in U : x \text{ has property } P_i\}$ recovers the set formulation exactly, so the two phrasings are identical in content. This predicate phrasing is often more natural when properties are combinatorial conditions (e.g., "the permutation fixes position $i$ ," or "the assignment violates constraint $j$ ") rather than naturally-occurring subsets, and it is the phrasing most commonly used when applying PIE to derangements, surjections, and constraint-satisfaction counting problems.