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

Difference between revisions of "Principle of Inclusion-Exclusion"

(→‎Proof)
(→‎Remarks)
Line 1: Line 1:
 
The '''Principle of Inclusion-Exclusion''' (abbreviated PIE) provides an organized method/formula to find the number of [[element]]s in the [[union]] of a given group of [[set]]s, the size of each set, and the size of all possible [[intersection]]s among the sets.
 
The '''Principle of Inclusion-Exclusion''' (abbreviated PIE) provides an organized method/formula to find the number of [[element]]s in the [[union]] of a given group of [[set]]s, the size of each set, and the size of all possible [[intersection]]s among the sets.
−
 
−
== Remarks ==
 
−
Sometimes it is also useful to know that, if you take into account only the first <math>m\le n</math> sums on the right, then you will get an overestimate if <math>m</math> is [[odd integer | odd]] and an underestimate if <math>m</math> is [[even integer | even]].
 
−
So,
 
−
 
−
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|</math>,
 
−
 
−
<math>\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|</math>,
 
−
 
−
<math>\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|</math>,
 
−
 
−
and so on.
 
  
 
== Examples ==
 
== Examples ==

Revision as of 15:57, 24 October 2020

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.

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

2017 AMC 10B Problems/Problem 13 https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10B_Problems/Problem_13

2005 AMC 12A Problems/Problem 18 https://artofproblemsolving.com/wiki/index.php/2005_AMC_12A_Problems/Problem_18

See also

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