Principle of Inclusion-Exclusion

Revision as of 11:48, 19 July 2017 by Brookings (talk | contribs) (Examples)

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.

Remarks

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,

and so on.

Examples

2002 AIME I Problems/Problem 1 http://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_1#Problem 2011 AMC 8 Problems/Problem 6 https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_8_Problems/Problem_6

See also