Difference between revisions of "Principle of Inclusion-Exclusion"

Line 14: Line 14:
== Examples ==
== Examples ==
* http://www.artofproblemsolving.com/Forum/viewtopic?t=83102
Don't have any.
* http://www.artofproblemsolving.com/Forum/viewtopic?t=61283
== See also ==
== See also ==

Revision as of 17:05, 18 September 2016

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.


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.


Don't have any.

See also

Invalid username
Login to AoPS