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"

m (none)
(→‎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><math> \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|
+
<center>$ \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>
+
 
 
== 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 18: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.

Statement

If $(A_i)_{1\leq i\leq n}$ are finite sets, then:

$ \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|

Remarks

Sometimes it is also useful to know that, if you take into account only the first $m\le n$ sums on the right, then you will get an overestimate if $m$ is odd and an underestimate if $m$ is even. So,

$\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|$,

$\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|$,

$\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|$,

and so on.

Examples

See also

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