# 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},\mathrm{\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.

Title | principle of inclusion-exclusion |
---|---|

Canonical name | PrincipleOfInclusionexclusion |

Date of creation | 2013-03-22 12:33:25 |

Last modified on | 2013-03-22 12:33:25 |

Owner | Mathprof (13753) |

Last modified by | Mathprof (13753) |

Numerical id | 9 |

Author | Mathprof (13753) |

Entry type | Theorem |

Classification | msc 05A99 |

Synonym | inclusion-exclusion principle |

Related topic | SieveOfEratosthenes2 |

Related topic | BrunsPureSieve |