| Version current |
Version 5 |
| The \emph{principle of inclusion-exclusion} provides a way of methodically counting the union of possibly non-disjoint sets. |
The \emph{principle of inclusion-exclusion} provides a way of methodically counting the union of possibly non-disjoint sets. |
|
|
| Let $C = \{A_1, A_2, \dots A_N\}$ be a finite collection of finite sets. Let $I_k$ represent the set of $k$-fold intersections of members of $C$ (e.g., $I_2$ contains all possible intersections of two sets chosen from $C$). |
Let $C = \{A_1, A_2, \dots A_N\}$ be a finite collection of finite sets. Let $I_k$ represent the set of $k$-fold intersections of members of $C$ (e.g., $I_2$ contains all possible intersections of two sets chosen from $C$). |
|
|
| Then |
Then |
| $$\left| \bigcup_{i=1}^{N} A_i \right| = \sum_{j=1}^N \left( (-1)^{(j+1)} \sum_{S \in I_j} |S| \right )$$ |
$$\left| \bigcup_{i=1}^{N} A_i \right| = \sum_{j=1}^N \left( (-1)^{(j+1)} \sum_{S \in I_j} |S| \right )$$ |
|
|
| For example: |
For example: |
| $$|A \cup B| = |A|+|B|-|A \cap B|$$ |
$$|A \cup B| = |A|+|B|-|A \cap B|$$ |
| $$|A \cup B \cup C| = |A|+|B|+|C|-(|A \cap B|+|A \cap C|+|B \cap C|)+|A \cap B \cap C|$$ |
$$|A \cup B \cup C| = |A|+|B|+|C|-(|A \cap B|+|A \cap C|+|B \cap C|)+|A \cap B \cap C|$$ |
|
|
| The principle of inclusion-exclusion, combined with de Morgan's laws, can be used to count the intersection of sets as well. Let $A$ be some universal set such that $A_k \subseteq A$ for each $k$, and let $\overline{A_k}$ represent the complement of $A_k$ with respect to $A$. Then we have |
The principle of inclusion-exclusion, combined with de Morgan's laws, can be used to count the intersection of sets as well. Let $A$ be some universal set such that $A_k \subseteq A$ for each $k$, and let $\overline{A_k}$ represent the complement of $A_k$ with respect to $A$. Then we have |
|
|
|
$$\left | \bigcap_{i=1}^N A_i \right | = \left |\overline{ \bigcup_{i=1}^N \overline{A_i} }\right |$$
|
$$\left | \bigcap_{i=1}^N A_i \right | = \overline{\left | \bigcup_{i=1}^N \overline{A_i} \right |}$$
|
|
|
| thereby turning the problem of finding an intersection into the problem of finding a union. |
thereby turning the problem of finding an intersection into the problem of finding a union. |
