Difference between revisions of "Principle of Inclusion-Exclusion"

Revision as of 20: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.

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| -\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|{}$ .

Proof

We prove that each element is counted once.

Say that some element $X$ is in $k$ sets. Without loss of generality, these sets are $A_1,A_2,\dots,A_k.$

We proceed by induction. This is obvious for $k=1.$

If this is true for $k,$ we prove this is true for $k+1.$ For every set of sets not containing $A_{k+1}$ with size $i,$ there is a set of sets containing $A_{k+1}$ with size $i+1.$ In PIE, the sum of how many times these sets are counted is $0.$ There is also one additional set of sets $\{A_{k+1}\},$ so $X$ is counted exactly once.

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

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

@@ 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.
+== 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 ==

Page

Toolbox

Search