Principle of Inclusion/Exclusion

Overview

The principle of inclusion/exclusion (PIE) refers to the process of adding and subtracting, used to find the cardinality of potentially overlapping sets. Given finite sets $A_{1}, A_{2}, \dots, A_{n}$ the following identity captures the concept:

| ⋃_{k = 1}^{n} A_{k} | = \sum_{k = 1}^{n} (- 1)^{k + 1} (\sum_{1 \leq i_{1} < \dots < i_{k} \leq n} | A_{i_{1}} \cap \dots \cap A_{i_{k}} |)

For example, given finite sets $A$ , $B$ , and $C$ ,

\begin{aligned} | A \cup B | & = | A | + | B | - | A B | \\ | A \cup B \cup C | & = | A | + | B | + | C | - | A B | - | A C | - | B C | + | A B C | \end{aligned}

The number of terms containing one set, two sets, three sets, etc. match the binomial coefficients.

Probability

The principle of inclusion-exclusion also holds in probability. Let $A_{1}, A_{2}, \dots, A_{n}$ be a number of events in a shared sample space. Then

P (⋃_{k = 1}^{n} A_{k}) = \sum_{k = 1}^{n} (- 1)^{k + 1} (\sum_{1 \leq i_{1} < \dots < i_{k} \leq n} P (A_{i_{1}} \cap \dots \cap A_{i_{k}})) .

For example, given events $A$ , $B$ , and $C$ ,

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

Minimum/Maximum

The $min$ and $max$ operations respect the principle of inclusion/exclusion. In particular,

\begin{aligned} min (a_{1}, \dots, a_{n}) & = \sum_{k = 1}^{n} (- 1)^{k + 1} (\sum_{1 \leq i_{1} < \dots < i_{k} \leq n} max (a_{i_{1}}, \dots, a_{i_{k}})) \\ max (a_{1}, \dots, a_{n}) & = \sum_{k = 1}^{n} (- 1)^{k + 1} (\sum_{1 \leq i_{1} < \dots < i_{k} \leq n} min (a_{i_{1}}, \dots, a_{i_{k}})) \end{aligned}