principle of inclusion-exclusion

The principle of inclusion-exclusion provides a way of methodically counting the union of possibly non-disjoint sets.

Let C={A1,A2,AN} be a finite collectionMathworldPlanetmath of finite setsMathworldPlanetmath. Let Ik represent the set of k-fold intersectionsMathworldPlanetmathPlanetmath of members of C (e.g., I2 contains all possible intersections of two sets chosen from C).



For example:


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 AkA for each k, and let Ak¯ represent the complement of Ak with respect to A. Then we have


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