Inclusion-Exclusion Principle

The Problem with Unions

When computing $P(E \cup F)$, we cannot simply add $P(E) + P(F)$ because outcomes in $E \cap F$ get counted twice.

Two-Event Inclusion-Exclusion

$P(E \cup F) = P(E) + P(F) - P(E \cap F)$

Intuition: Add probabilities of each event, then subtract the intersection to correct for double-counting.

Example: Cards

Draw a card. Let $E$ = “heart” and $F$ = “ace”.

$P(E \cup F) = \frac{13}{52} + \frac{4}{52} - \frac{1}{52} = \frac{16}{52} = \frac{4}{13}$

Verify directly: 13 hearts + 3 other aces = 16 cards out of 52.

Three-Event Inclusion-Exclusion

$P(E \cup F \cup G) = P(E) + P(F) + P(G) - P(E \cap F) - P(E \cap G) - P(F \cap G) + P(E \cap F \cap G)$

Pattern: Add singletons, subtract pairs, add triples. The signs alternate.

Why Add the Triple?

Each element in $E \cap F \cap G$:

• Counted 3 times in singletons (+3)
• Counted 3 times in pairs (−3)
• Not yet counted in triples (+0)

We need +1 total, so add $P(E \cap F \cap G)$.

General Formula

For $n$ events $E_1, E_2, \ldots, E_n$:

$P\left(\bigcup_{i=1}^{n} E_i\right) = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} P(E_{i_1} \cap E_{i_2} \cap \cdots \cap E_{i_k})$

In words: sum probabilities of $k$-fold intersections with sign $(-1)^{k+1}$.

Example: Hat Check Problem

$n$ people throw their hats into a pile. Each picks a hat randomly. What is the probability at least one person gets their own hat?

Let $E_i$ = person $i$ gets their own hat.

$P\left(\bigcup_{i=1}^{n} E_i\right) = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} \frac{(n-k)!}{n!}$

• $P(E_i) = \frac{1}{n}$ for each of $\binom{n}{1}$ choices
• $P(E_i \cap E_j) = \frac{(n-2)!}{n!}$ for $\binom{n}{2}$ pairs
• Generally: $P$($k$ specific people get their hats) $= \frac{(n-k)!}{n!}$

This gives:

$P(\text{at least one match}) = \sum_{k=1}^{n} (-1)^{k+1} \frac{1}{k!}$

As $n \to \infty$, this approaches $1 - e^{-1} \approx 0.632$.

The Complement View

For complex unions, computing $P(\text{none})$ via complement is often easier.

$P\left(\bigcup_{i=1}^{n} E_i\right) = 1 - P\left(\bigcap_{i=1}^{n} E_i^c\right)$

When events are independent: $P(\text{all fail}) = \prod P(E_i^c)$, giving:

$P(\text{at least one}) = 1 - \prod_{i=1}^{n}(1 - P(E_i))$

Example: Reliability

A system has 3 components, each failing independently with probability 0.1. What is the probability the system fails (at least one component fails)?

$P(\text{system fails}) = 1 - P(\text{all work}) = 1 - 0.9^3 = 1 - 0.729 = 0.271$

Inclusion-Exclusion for Counting

The principle applies to counting, not just probability:

$|\bigcup_{i=1}^{n} A_i| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \leq i_1 < \cdots < i_k \leq n} |A_{i_1} \cap \cdots \cap A_{i_k}|$

Example: Integer Properties

How many integers from 1 to 1000 are divisible by 2 or 3?

Let $A$ = multiples of 2, $B$ = multiples of 3.

• $|A| = \lfloor 1000/2 \rfloor = 500$
• $|B| = \lfloor 1000/3 \rfloor = 333$
• $|A \cap B|$ = multiples of 6: $\lfloor 1000/6 \rfloor = 166$

$|A \cup B| = 500 + 333 - 166 = 667$

Bonferroni Inequalities

The partial sums in inclusion-exclusion alternate between over- and under-estimates:

$P(E_1 \cup \cdots \cup E_n) \leq \sum_{i} P(E_i)$ $P(E_1 \cup \cdots \cup E_n) \geq \sum_{i} P(E_i) - \sum_{i<j} P(E_i \cap E_j)$

These provide upper and lower bounds when exact computation is impractical.

Summary

Events	Formula
2 events	$P(E) + P(F) - P(E \cap F)$
3 events	$P(E)+P(F)+P(G) - P(E \cap F) - P(E \cap G) - P(F \cap G) + P(E \cap F \cap G)$
$n$ events	$\sum_{k=1}^{n} (-1)^{k+1} \sum_{i_1 < \cdots < i_k} P(E_{i_1} \cap \cdots \cap E_{i_k})$
Complement	$1 - P(\bigcap E_i^c)$