## 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: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier