## You are here

Homeprinciple of inclusion-exclusion

## Primary tabs

# principle of inclusion-exclusion

The *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$).

Then

$\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:

$|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|$ |

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|$ |

thereby turning the problem of finding an intersection into the problem of finding a union.

## Mathematics Subject Classification

05A99*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: numerical method (implicit) for nonlinear pde by roozbe

new question: Harshad Number by pspss

Sep 14

new problem: Geometry by parag

Aug 24

new question: Scheduling Algorithm by ncovella

new question: Scheduling Algorithm by ncovella