The Inclusion–Exclusion Principle

The Basic Problem

When sets overlap, simply adding their sizes overcounts elements that lie in multiple sets.

Example with two sets:

• $A$: people who play pickleball
• $B$: people who do archery

If you just do $|A| + |B|$, then anyone who does both pickleball and archery is counted twice. The inclusion–exclusion principle is a systematic way to correct this overcounting.

Two-Set Inclusion–Exclusion

Statement

For two finite sets $A$ and $B$:

• Add the sizes of each set.
• Subtract the intersection, because those elements were counted twice.

Quick Concrete Example

Suppose in a club of students:

• 18 study French
• 25 study Physics
• 7 study both French and Physics

Then the number who study French or Physics (or both) is

A two-set diagram splits into three regions: each subject on its own, plus the overlap. Subtracting the 7 who study both from each subject's total leaves the "only" counts:

Three-Set Inclusion–Exclusion

With three sets, double-counting (and even triple-counting) becomes more subtle.

Let $A$, $B$, $C$ be finite sets. Then:

Pattern:

1. Add each single set.
2. Subtract each pairwise intersection.
3. Add the triple intersection.

Why This Pattern?

Think about one element $x$:

• If $x \in A \cap B \cap C$:
  • It gets counted once in each of $|A|$, $|B|$, $|C|$ → total 3 times.
  • It gets subtracted once in each of $|A \cap B|$, $|A \cap C|$, $|B \cap C|$ → subtracted 3 times.
  • So far, net contribution is $3 - 3 = 0$.
  • Then $|A \cap B \cap C|$ adds it once more → total 1, which is correct.
• If $x$ lies in exactly two sets, say $A$ and $B$ but not $C$:
  • Counted twice in $|A| + |B| + |C|$.
  • Subtracted once in $|A \cap B|$.
  • Not in the other intersections.
  • Net: $2 - 1 = 1$, which is correct.
• If $x$ lies in exactly one set, say only $A$:
  • Counted once in $|A|$.
  • Not in any intersections.
  • Net: 1, correct.

So every element in the union contributes exactly 1.

Example with Three Sets

Think of students in a discrete math class:

• $A$: use macOS
• $B$: use Linux
• $C$: use Windows

Crucially, these sets overlap: a student may use more than one operating system — for instance across different devices, or by dual-booting a single machine. So a student can belong to two of the sets, or even all three. That is exactly why the intersection counts below are nonzero.

Suppose:

• $|A| = 15$, $|B| = 12$, $|C| = 20$
• $|A \cap B| = 4$, $|A \cap C| = 5$, $|B \cap C| = 6$
• $|A \cap B \cap C| = 2$

Then:

So 34 students use at least one of the three systems.

The diagram below shows why. A three-set diagram splits into seven disjoint regions. Working from the centre outward — subtract the triple overlap from each pairwise overlap, then subtract all of those from each circle's total — gives the count of students in exactly those sets:

The General $n$-Set Formula

For sets $A_1, A_2, \dots, A_n$, the Inclusion–Exclusion Principle says:

Intuition: each element that lies in exactly $k$ of the sets gets counted

so every element in the union ends up counted exactly once.

Decoding the Compact Notation

The expanded formula above — add the singles, subtract the pairs, add back the triples, and so on — can be packaged into a single compact expression:

This is the form you will most often meet in textbooks. It looks dense, but it has just two working parts: a sign-switcher $(-1)^{k+1}$ and an inner sum that gathers every $k$-way intersection. We decode each piece below.

What is $S$?

$S$ is a subset of the index set $\{1, 2, \dots, n\}$. The indices are simply labels for the sets. For example, with sets $A_1, A_2, A_3$, the subsets of size $2$ are $\{1,2\},\ \{1,3\},\ \{2,3\}$ — each one names a particular pair of sets to intersect.

What does $|S| = k$ mean?

The condition $|S| = k$ under the inner $\sum$ means: sum over all subsets $S$ that have exactly $k$ elements. As $k$ climbs, $S$ ranges over deeper levels of overlap:

• $k = 1$: $S$ ranges over $\{1\}, \{2\}, \{3\}, \dots$ — each individual set.
• $k = 2$: $S$ ranges over $\{1,2\}, \{1,3\}, \{2,3\}, \dots$ — every pair.
• $k = 3$: $S$ ranges over $\{1,2,3\}, \dots$ — every triple.

What does $\bigcap_{i \in S} A_i$ mean?

This is the intersection of all sets whose index lies in $S$. For example, if $S = \{1, 3\}$, then

The vertical bars $\left|\,\cdot\,\right|$ around it denote the size (cardinality) of that intersection. So the inner sum $\sum_{|S|=k}\left|\bigcap_{i \in S} A_i\right|$ reads: find every combination of $k$ sets, take the size of their intersection, and add all those sizes together. For $k=2$ with three sets it produces exactly the pairwise step $|A_1 \cap A_2| + |A_1 \cap A_3| + |A_2 \cap A_3|$.

The role of $(-1)^{k+1}$

The factor $(-1)^{k+1}$ is what "alternating signs" means in precise language. It equals $+1$ when $k$ is odd (add) and $-1$ when $k$ is even (subtract):

Compact $\to$ expanded. Stepping the compact formula through $k = 1, 2, 3$ for three sets recovers the expanded three-set formula from earlier:

• $k=1$: $(-1)^{2} = +1$, so add $|A_1| + |A_2| + |A_3|$.
• $k=2$: $(-1)^{3} = -1$, so subtract $|A_1 \cap A_2| + |A_1 \cap A_3| + |A_2 \cap A_3|$.
• $k=3$: $(-1)^{4} = +1$, so add back $|A_1 \cap A_2 \cap A_3|$.

The compact notation simply lets the loop variable $k$ and the sign-switcher $(-1)^{k+1}$ generate every level automatically, instead of writing each line out by hand.

Typical Problem Types

A. "At Least One" Counting Problems

Example: "How many integers from 1 to 1000 are divisible by 3 or 5 or 7?"

Let $A$ = multiples of 3, $B$ = multiples of 5, $C$ = multiples of 7. The number of multiples of $m$ in $\{1, \dots, 1000\}$ is $\left\lfloor 1000/m \right\rfloor$, and an integer is divisible by two of the moduli exactly when it is divisible by their least common multiple (here the moduli are coprime, so the lcm is just the product).

• Single sets: $|A| = \lfloor 1000/3 \rfloor = 333$, $|B| = \lfloor 1000/5 \rfloor = 200$, $|C| = \lfloor 1000/7 \rfloor = 142$.
• Pairwise: $|A \cap B| = \lfloor 1000/15 \rfloor = 66$, $|A \cap C| = \lfloor 1000/21 \rfloor = 47$, $|B \cap C| = \lfloor 1000/35 \rfloor = 28$.
• Triple: $|A \cap B \cap C| = \lfloor 1000/105 \rfloor = 9$.

Applying the three-set formula:

So 543 of the integers from 1 to 1000 are divisible by 3, 5, or 7.

B. Avoiding Properties

Sometimes it is easier to count objects that violate a rule and then subtract from a total. The key identity is that the number of elements of a universe $U$ avoiding every property is the total minus the size of the union:

Example: counting permutations of $\{1, \dots, n\}$ where no element stays fixed (these are called derangements).

• Take $U$ to be all $n!$ permutations.
• Let $A_i$ be the set of permutations that fix element $i$.
• A permutation fixing a chosen set of $k$ elements is free to permute the rest, so any $k$-fold intersection has size $(n-k)!$, and there are $\binom{n}{k}$ ways to choose which $k$ are fixed.

The permutations with no fixed point are those avoiding every $A_i$, so by the complement identity above:

For example, $D_3 = 6\left(1 - 1 + \tfrac{1}{2} - \tfrac{1}{6}\right) = 2$ and $D_4 = 24\left(1 - 1 + \tfrac{1}{2} - \tfrac{1}{6} + \tfrac{1}{24}\right) = 9$.

General Strategy for New Problems

1. Define sets $A_i$ capturing each "condition" in the problem.
2. Compute intersection sizes $|A_i|$, $|A_i \cap A_j|$, etc.
3. Decide how many levels of intersections are actually needed.
4. Apply inclusion–exclusion with alternating signs.
5. Interpret the result in terms of the original question.

Where to Go Next

To deepen your understanding, pick an angle and work a full example end to end. Good starting points include:

• a concrete counting problem (like multiples of 3, 5, 7),
• a probability problem, or
• a proof-oriented derivation of the general formula.