Generalized Inclusion-Exclusion Formula

Why

If $A$ and $B$ are two events in some finite sample space $\Omega $ and $P$ is the event probability function of some distribution, we have seen that

\[ P(A \cup B) = P(A) + P(B) - P(A \cap B) \]

What if we have three events $A, B, C$? What of a list of $n$ events $A_1, \dots , A_n$?

Case of $n = 3$.

Suppose $A, B, C$ are events in a finite sample space and $P$ is any event probability function. Then

\[ \begin{aligned} P(A \cup B \cup C) = P&(A) + P(B) + P(C) \\ &- P(A \cap B) - P(A \cap C) - P(B \cap C) \\ &+ P(A \cap B \cap C) \end{aligned} \]

Express

\[ \begin{aligned} P(A \cup B \cup C) &= P(A \cup B) + P(C) - P((A \cup B) \cap C) \\ &= P(A) + P(B) + P(C) - P(A \cap B) - P((A \cup B) \cap C) \\ \end{aligned} \]

by using the inclusion-exclusion formula. Recall¹ that

\[ (A \cup B) \cap C = (A \cap C) \cup (B \cap C) \]

Now use the inclusion-exclusion formula again, and properties of set pair intersections to get

\[ \begin{aligned} P((A \cup B) \cap C) &= P(A \cap C) + P(B \cap C) - P((A \cap C) \cap (B \cap C)) \\ &= P(A \cap C) + P(B \cap C) - P(A \cap B \cap C) \\ \end{aligned} \]

Case of $n$.

Suppose $A_1, \dots , A_n,$ are events in a finite sample space and $P$ is any event probability function. Then

\[ \begin{aligned} P(A_1 \cup \cdots \cup A_n) = \sum P&(A_i) -\sum P(A_i \cap A_j) \\ &\sum P(A_i \cap A_j \cap A_k) - \cdots \\ &(-1)^{n-1} P(A_1 \cap \cdots A_n) \end{aligned} \]

This can be shown by induction on the number of events $n$. Future editions will include.

Here there are ${n \choose r}$ terms in the $r$th sum, $r = 1, \dots , n$.

See Set Unions and Intersections. ↩︎