Inclusion-Exclusion

Imagine you want to count the integers from 1 to 1000 that are divisible by 2, by 3, or by both. You can't just add the two groups — you'd count multiples of 6 twice. So you subtract them back. That one fix is the entire soul of inclusion-exclusion.

The principle generalizes immediately: to count the integers that fall in at least one of several sets, alternately add all individual set sizes, subtract all pairwise intersections, add all triple intersections, and so on. Every object gets counted exactly once no matter how many sets it belongs to.

Written as a formula for sets $A_{1}$, $A_{2}$, …, $A_{n}$:

$$|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum|A_i| - \sum|A_i \cap A_j| + \sum|A_i \cap A_j \cap A_k| - \cdots$$

The alternating signs come from the binomial theorem: an element belonging to exactly $k$ of the sets is counted $\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots = 1$ times overall. This is a classical result of combinatorics; it was known to Sylvester (1879) and Poincaré in various forms.

The principle is solved mathematics — the formula is exact and its proof is elementary — but its role in algorithm design continues to surprise: it converts exponential brute-force searches into structured alternating sums that can be evaluated in polynomial or quasi-polynomial time for problems that look much harder.

Pick a few primes below and watch the principle count integers from 1 to 999 that are not divisible by any of them — that is, coprime to the product of your chosen primes.

<p class="hint">{{hint}}</p>
<div class="prime-row" id="prime-row"></div>
<div id="steps" class="steps"></div>
<div class="result-line" id="result-line"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .75rem; line-height: 1.45; }
.prime-row { display: flex; flex-wrap: wrap; gap: .4rem; margin-bottom: .9rem; }
.prime-btn {
  padding: .35rem .7rem; border-radius: 20px; border: 1.5px solid #1d3557;
  background: #fff; color: #1d3557; font: 600 14px system-ui; cursor: pointer;
  transition: background .12s, color .12s;
}
.prime-btn.active { background: #1d3557; color: #fff; }
.steps { font-size: .88rem; line-height: 1.7; }
.step-row { display: flex; gap: .4rem; align-items: baseline; }
.step-level { min-width: 5.4rem; color: #666; font-size: .82rem; }
.step-term { font-family: ui-monospace, monospace; color: #1d3557; }
.step-sign { font-weight: 700; color: #c92f3c; min-width: 1.2rem; text-align: center; }
.step-sign.plus { color: #0a7d33; }
.running { color: #555; font-size: .82rem; }
.result-line {
  margin-top: .8rem; font-size: 1.05rem; font-weight: 700; color: #0a7d33;
  min-height: 1.5em;
}

// Code not found

The demo expands the alternating sum one level at a time. Notice that each level can only increase or decrease the running total by a bounded amount — the formula converges quickly even though the raw union could involve hundreds of numbers.

The inclusion-exclusion formula is elementary and exact — no approximation, no randomness. But what makes it algorithmically powerful is how it trades one hard enumeration for many easier ones.

Derangements. How many permutations of $n$ objects have no fixed point? A direct count seems hard, but inclusion-exclusion over the $n$ sets "element $i$ is fixed" gives the exact answer $D(n) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ in $O(n)$ time.

DNF counting (#P-hard). Counting satisfying assignments of a Disjunctive Normal Form formula is #P-complete — as hard as summing over all witnesses for an NP problem. A randomized inclusion-exclusion scheme (Karp–Luby, 1983) gives a fully polynomial-time randomized approximation scheme (FPRAS), one of the few #P problems known to admit one.

Set cover and Steiner tree. The fastest known exact algorithms for set cover and related problems run in O($2^{n}$ · poly(n)) time using inclusion-exclusion over subsets — far better than naive $O(3^{n})$ enumeration. Björklund and Husfeldt (2008) used this to solve Steiner tree exactly in O($2^{n}$ · poly(n)) for the first time.

The #P boundary. The principle itself is in P — you can evaluate the alternating sum in polynomial time when the intersection sizes are easy to compute. The hardness kicks in only when the sets themselves are implicit (given by a formula or a graph), making intersection sizes hard to compute. That is why inclusion-exclusion is a tool, not a problem: its complexity is borrowed from whatever you apply it to.

This connects directly to counting #P: many #P problems become tractable or approximable precisely because they can be expressed as an inclusion-exclusion sum over polynomial-time-computable terms.

"Count things satisfying at least one condition" appears everywhere, and inclusion-exclusion is the universal tool:

• Probability theory: the union bound and its refinements (Bonferroni inequalities) all flow from the inclusion-exclusion identity. Every probabilistic argument that bounds the chance of any bad event uses it.
• Derangements and combinatorics: counting permutations with forbidden positions, tilings with forbidden tiles, and surjective functions all reduce to alternating sums.
• Cryptanalysis: the meet-in-the-middle attack on block ciphers counts key collisions using set intersection arguments that are formally inclusion-exclusion.
• Exact exponential algorithms: the best known exact algorithms for set cover, Steiner tree, and chromatic polynomial all run in $O(2^{n})$ using inclusion-exclusion over subsets, replacing slower enumeration methods.
• Network reliability: computing the probability that a network stays connected despite random link failures is a union-of-events problem solved by inclusion-exclusion over minimal cut sets.
• Sieve methods in number theory: the Sieve of Eratosthenes and its modern descendants (Legendre sieve, Brun sieve) are all specializations of inclusion-exclusion over sets of multiples of primes.

The principle's reach is unusual: it is simple enough to teach in a first combinatorics course yet deep enough to drive the state of the art in exact exponential algorithms.

Inclusion-exclusion is one of those rare ideas that is both completely understood and inexhaustibly useful. The formula is proven, exact, and elementary — yet it keeps appearing at the frontier: in the fastest algorithms for set cover and Steiner tree, in the theory of #P-hard counting problems, in the sieves of analytic number theory.

The next time you count something and worry about double-counting, remember: add, subtract, add, subtract. The alternating signs cancel every overlap exactly, and that simple rhythm has been quietly powering mathematics and algorithms for well over a century.