Principle of Inclusion-Exclusion

Revision as of 16:57, 24 October 2020 by Mathpro12345 (talk | contribs) (Statement)

The Principle of Inclusion-Exclusion (abbreviated PIE) provides an organized method/formula to find the number of elements in the union of a given group of sets, the size of each set, and the size of all possible intersections among the sets.


We prove that each element is counted once.

Say that some element $X$ is in $k$ sets. Without loss of generality, these sets are $A_1,A_2,\dots,A_k.$

We proceed by induction. This is obvious for $k=1.$

If this is true for $k,$ we prove this is true for $k+1.$ For every set of sets not containing $A_{k+1}$ with size $i,$ there is a set of sets containing $A_{k+1}$ with size $i+1.$ In PIE, the sum of how many times these sets are counted is $0.$ There is also one additional set of sets $\{A_{k+1}\},$ so $X$ is counted exactly once.


Sometimes it is also useful to know that, if you take into account only the first $m\le n$ sums on the right, then you will get an overestimate if $m$ is odd and an underestimate if $m$ is even. So,

$\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|$,

$\left|\bigcup_{i=1}^n A_i\right|\ge \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right|$,

$\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|$,

and so on.


2002 AIME I Problems/Problem 1

2011 AMC 8 Problems/Problem 6

2017 AMC 10B Problems/Problem 13

2005 AMC 12A Problems/Problem 18

See also

Invalid username
Login to AoPS