# Difference between revisions of "Principle of Inclusion-Exclusion"

(Undo revision 135755 by Mathpro12345 (talk)) (Tag: Undo) |
(Undo revision 135754 by Mathpro12345 (talk)) (Tag: Undo) |
||

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 19:42, 26 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.

## Remarks

Sometimes it is also useful to know that, if you take into account only the first sums on the right, then you will get an overestimate if is odd and an underestimate if 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

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