Skip to main content

Inclusion-Exclusion as Overlap Accounting

What This Concept Is​

Inclusion-exclusion counts a union of overlapping sets by correcting the overcount created by naive addition. For two sets:

$$|A \cup B| = |A| + |B| - |A \cap B|.$$

For three sets:

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$$

In general, for sets $A_1, \ldots, A_n$:

$$\left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1} \sum_{I \subseteq {1,\ldots,n},,|I|=k} \left|\bigcap_{i \in I} A_i\right|.$$

The sign pattern alternates because each layer corrects the mistakes of the previous one. An element in exactly $m$ of the sets gets counted $\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots = 1$ times, by the binomial identity $\sum_{k} (-1)^{k+1} \binom{m}{k} = 1$ for $m \ge 1$. That identity is the reason inclusion-exclusion works.

Equivalently, inclusion-exclusion can be stated as a complement form: to count objects with none of a set of forbidden properties $P_1, \ldots, P_n$, compute

$$\left|\overline{A_1} \cap \cdots \cap \overline{A_n}\right| = \sum_{I \subseteq {1,\ldots,n}} (-1)^{|I|} \left|\bigcap_{i \in I} A_i\right|,$$

where $A_i$ is the set of objects with property $P_i$. This "avoid all forbidden properties" form is the workhorse version for derangements and forbidden-pattern counting.

Two ways to see why the signs alternate: (a) binomial identity $\sum_{k \ge 1} (-1)^{k+1}\binom{m}{k} = 1$ for $m \ge 1$ -- each element's contribution telescopes to exactly $1$; (b) expanding the product $\prod_i (1 - \mathbf{1}{A_i})$ -- each $(-1)^{|I|}$ factor comes from choosing the $\mathbf{1}{A_i}$ term in each factor $i \in I$. Pick whichever proof you find memorable; both recur across probability, combinatorics, and number theory.

Why It Matters Here​

Many constrained counting problems are "count all objects, then remove the forbidden ones." That fails when objects violate several constraints at once. Inclusion-exclusion is the disciplined repair: count each forbidden-property set, their pairwise intersections, their triple intersections, and so on with alternating signs.

It is also a conceptual bridge to probability: the same logic underlies the union bound in reverse ($P(A \cup B) = P(A) + P(B) - P(A \cap B)$), which you revisit in Module 3, and reliability analysis in Module 6 distributed systems.

The formula is not deep. What is deep is noticing when to invoke it -- typically when the complement is easy but the direct count is messy.

Indicator-function view. Many modern proofs write inclusion-exclusion as an identity between indicator functions: $\mathbf{1}{A_1 \cup \cdots \cup A_n} = 1 - \prod_i (1 - \mathbf{1}{A_i})$. Expanding the product and summing recovers the classical formula; this viewpoint generalizes cleanly to weighted counts (Möbius inversion on a poset) and to probability theory (inclusion-exclusion for events).

Concrete Examples​

Example 1: divisibility. How many integers from $1$ to $100$ are divisible by $2$ or $3$?

Let $A$ = multiples of $2$, $B$ = multiples of $3$. Then $|A| = \lfloor 100/2 \rfloor = 50$, $|B| = \lfloor 100/3 \rfloor = 33$, and $|A \cap B|$ = multiples of $\text{lcm}(2,3) = 6$, which is $\lfloor 100/6 \rfloor = 16$. Therefore:

$$|A \cup B| = 50 + 33 - 16 = 67.$$

The $16$ multiples of $6$ were double-counted by the naive sum; the subtraction repairs it.

Example 2: derangements. How many permutations of ${1, 2, \ldots, n}$ fix no element? (These are called derangements and arise in the hat-check problem: $n$ guests check $n$ hats, and all hats are returned with every guest getting the wrong hat.)

Let $A_i$ = permutations that fix element $i$. We want $|\overline{A_1} \cap \cdots \cap \overline{A_n}|$. By inclusion-exclusion:

$$D_n = \sum_{k=0}^n (-1)^k \binom{n}{k}(n-k)! = n! \sum_{k=0}^n \frac{(-1)^k}{k!}.$$

Reasoning: $|A_{i_1} \cap \cdots \cap A_{i_k}|$ = permutations fixing a specified $k$-subset of positions = $(n-k)!$, and there are $\binom{n}{k}$ such subsets.

For $n = 4$: $D_4 = 4!(1 - 1 + 1/2 - 1/6 + 1/24) = 24 \cdot (9/24) = 9$. Check by brute enumeration: there are indeed $9$ derangements of ${1,2,3,4}$. As $n \to \infty$, $D_n / n! \to 1/e \approx 0.368$; roughly $37%$ of random permutations are derangements regardless of $n$.

Example 3: surjection counting. How many functions $f: [n] \to [k]$ are surjective (every output is hit)?

Let $A_i$ = functions that miss output $i$. We want $|\overline{A_1} \cap \cdots \cap \overline{A_k}|$. For a fixed subset $I$ of the $k$ output labels with $|I| = j$, the number of functions avoiding all outputs in $I$ is $(k-j)^n$ (each of $n$ inputs chooses from $k-j$ allowed outputs). By inclusion-exclusion,

$$\text{Surj}(n, k) = \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n.$$

These are the Stirling numbers of the second kind scaled by $k!$: $\text{Surj}(n, k) = k! \cdot S(n, k)$, where $S(n,k)$ counts partitions of an $n$-set into $k$ non-empty blocks. This identity underlies analyses of hash uniformity, random coloring, and coupon-collector-like problems in Semester 3.

Common Confusion / Misconceptions​

  • Subtracting overlaps that were never counted twice. If $A$ and $B$ are disjoint, $|A \cap B| = 0$ and inclusion-exclusion just becomes plain addition. Applying it to disjoint sets adds bookkeeping with no payoff.
  • Forgetting higher-order intersections. For three sets, the triple intersection must be added back. Novice attempts often write $|A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C|$ and stop there, which undercounts elements that are in all three.
  • Unclear forbidden-property sets. The method is only as good as the chosen property sets. If $A_i$ is fuzzy or poorly defined, the intersections collapse or become impossible to compute.
  • Sign confusion. The sign on the $k$-fold intersection is $(-1)^{k+1}$ in the union form or $(-1)^k$ in the complement form. Writing both forms in the same argument without labeling gets signs wrong.
  • Unclear object identity. Define the finite sets and their intersection consistently; their union supplies a common containing universe. Different original ambient sets do not make an intersection intrinsically meaningless.
  • Applying IE to weighted sums without care. Probability versions (Bonferroni) truncate the alternating series for conservative bounds; stopping early yields bounds, not equalities. Know whether you want equality or bound.

How To Use It​

Use inclusion-exclusion when:

  1. you can describe forbidden (or desired) properties as sets $A_i$
  2. direct counting of the allowed objects is messy
  3. intersections $|\bigcap A_i|$ are comparatively easy (e.g., fixing $k$ positions reduces to counting permutations of the rest)
  4. the number of sets is small enough that $2^n$ intersection terms remain tractable

Operationally:

  1. define the property sets $A_1, \ldots, A_n$ clearly in words.
  2. compute single-set sizes $|A_i|$.
  3. compute pairwise intersections $|A_i \cap A_j|$.
  4. continue to higher intersections if needed, noting any symmetry that makes all $k$-fold intersections equal.
  5. keep signs consistent -- write the formula once and substitute.
  6. verify on a small instance by direct enumeration before trusting the general answer.
  7. consider the complement: sometimes "count objects avoiding all $P_i$" is cleaner than "count objects with at least one $P_i$."
  8. if $n$ is large but most intersections collapse (e.g., $A_i \cap A_j = \varnothing$ for many pairs), the series has short effective length. Exploit sparsity.
  9. if a symmetry makes all $k$-fold intersections equal in size, the sum reduces to $\binom{n}{k}$ times one intersection size -- write it out and save half the work.

Transfer to the workshop model​

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

Check Yourself​

  1. Why does naive addition fail for unions? Which elements get overcounted, and by how much?
  2. Why is the triple intersection added back in the three-set formula? Trace an element in all three sets through the formula.
  3. When is complement counting plus inclusion-exclusion better than direct enumeration?
  4. Derive the two-set formula from the three-set formula by setting $C = \varnothing$.
  5. Why does $D_n / n! \to 1/e$? Point to the Taylor series for $e^{-1}$.
  6. For $n = 5$ sets of sizes $|A_i| = 10$ each, with all pairwise intersections of size $3$, triple intersections of size $1$, and higher intersections empty: compute $|\bigcup_i A_i|$ by inclusion-exclusion.
  7. What is the sign of the $k$-fold intersection in the "avoid all forbidden properties" form? Why does the sign flip compared to the "union" form?

Mini Drill or Application​

  1. Count the integers from $1$ to $200$ divisible by at least one of $2$, $3$, or $5$. Write the set definitions explicitly.
  2. How many permutations of ${1, \ldots, 6}$ send at least one of $1, 2, 3$ to itself?
  3. Count surjections from an $n$-set to a $k$-set using inclusion-exclusion (property $A_i$ = "$i$ is not in the image").
  4. Count binary strings of length $10$ that do not contain 000 as a substring. (Hint: complement form on positions where 000 could start.)
  5. Verify $D_5 = 44$ using the inclusion-exclusion sum.
  6. Count the number of onto functions $[6] \to [3]$ using the surjection formula. Cross-check against $3! \cdot S(6, 3) = 6 \cdot 90 = 540$.
  7. Using inclusion-exclusion on "multiple of $p$" events for primes $p \le \sqrt{N}$, relate the count of integers $\le N$ coprime to $\prod p_i$ to Euler's totient.

Read This Only If Stuck​

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

Empty functions and impossible intersections​

For onto maps from n labeled inputs to k labeled outputs, let Aᵢ be the maps omitting output i. An intersection omitting j specified outputs has (k−j)^n maps, giving the alternating sum over j. In finite counting, 0⁰=1 records the one empty function. This yields one map when n=k=0, zero onto maps when n=0<k, and zero total maps when k=0<n.

In bounded distributions, intersecting forbidden events may make the residual total negative. That intersection then contains zero objects; do not feed the negative total into an ordinary factorial formula. Transfer: solve P6 and explain why all pairwise overflow intersections are empty.

After your attempt use practice feedback and model contracts to check the argument.