Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus
During AMC 10A/12A testing, the AoPS Wiki is in read-only mode and no edits can be made.

Principle of Inclusion-Exclusion: Difference between revisions

← Older editNewer edit →
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.

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,

$\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.

Examples

Don't have any.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Principle_of_Inclusion-Exclusion&oldid=80318"