Difference between revisions of "Principle of Inclusion-Exclusion"
(Undo revision 135753 by Mathpro12345 (talk)) (Tag: Undo) |
(Undo revision 135752 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. | ||
+ | |||
+ | == Statement == | ||
+ | If <math>(A_i)_{1\leq i\leq n}</math> are finite sets, then: | ||
+ | <center><math> \left|\bigcup_{i=1}^n A_i\right|=\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|-\cdots\ +(-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|{}</math>.</center> | ||
== Proof == | == Proof == |
Revision as of 19:43, 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.
Contents
[hide]Statement
If are finite sets, then:
Proof
We prove that each element is counted once.
Say that some element is in sets. Without loss of generality, these sets are
We proceed by induction. This is obvious for
If this is true for we prove this is true for For every set of sets not containing with size there is a set of sets containing with size In PIE, the sum of how many times these sets are counted is There is also one additional set of sets so is counted exactly once.
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