Difference between revisions of "Principle of Inclusion-Exclusion"
Forthewin1 (talk | contribs) m (none) |
Forthewin1 (talk | contribs) (→Statement) |
||
Line 3: | Line 3: | ||
== Statement == | == Statement == | ||
If <math>(A_i)_{1\leq i\leq n}</math> are finite sets, then: | If <math>(A_i)_{1\leq i\leq n}</math> are finite sets, then: | ||
− | <center> | + | <center>$ \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right| |
− | + | ||
== Remarks == | == 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]]. | 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]]. |
Revision as of 17:02, 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.
Contents
[hide]Statement
If are finite sets, then:
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
- http://www.artofproblemsolving.com/Forum/viewtopic?t=83102
- http://www.artofproblemsolving.com/Forum/viewtopic?t=61283