Difference between revisions of "Principle of Inclusion-Exclusion"
m (proofreading) |
(→Statement) |
||
Line 20: | Line 20: | ||
<center><math> \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right| | <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 \left|A_1\cap\cdots\cap A_n\right|{}. </math></center> | -\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 \left|A_1\cap\cdots\cap A_n\right|{}. </math></center> | ||
+ | == Remark == | ||
+ | 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 and an underestimate if <math>m</math> is 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 20:48, 29 June 2006
Contents
[hide]Introduction
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.
Two Set Example
Assume we are given the sizes of two sets, and and the size of their intersection, . We wish to find the size of their union, .
To find the union, we can add and . In doing so, we know we have counted everything in at least once. However, some things were counted twice. The elements that were counted twice are precisely those in . Thus, we have that:
Three Set Example
Assume we are given the sizes of three sets, and , the size of their pairwise intersections, and , and the size their overall intersection, . We wish to find the size of their union, .
Just like in the Two Set Example, we start with the sum of the sizes of the individual sets . We have counted the elements which are in exactly one of the original three sets once, but we've obviously counted other things twice, and even other things thrice! To account for the elements that are in two of the three sets, we first subtract out . Now we have correctly accounted for them since we counted them twice originally, and just subtracted them out once. However, the elements that are in all three sets were originally counted three times, and then subtracted out three times. We have to add back in . Putting this all together gives:
Statement
If are finite sets, then:
Remark
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
- http://www.artofproblemsolving.com/Forum/viewtopic?t=83102
- http://www.artofproblemsolving.com/Forum/viewtopic?t=61283