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"
(proofreading, changed number from 3 to 5 for all classes in example problem)
Line 3: Line 3:
  
 
=== Two Set Example ===
 
=== Two Set Example ===
−
Assume we are given the sizes of two sets, <math>|A_1|</math> and <math>|A_2|</math> and the size of their [[intersection]], <math>|A_1\cap A_2|</math>.  We wish to find the size of their union, <math>|A_1\cup A_2|</math>.
+
Assume we are given the sizes of two sets, <math>|A_1|</math> and <math>|A_2|</math>, and the size of their [[intersection]], <math>|A_1\cap A_2|</math>.  We wish to find the size of their union, <math>|A_1\cup A_2|</math>.
  
 
To find the union, we can add <math>|A_1|</math> and <math>|A_2|</math>.  In doing so, we know we have counted everything in <math>|A_1\cup A_2|</math> at least once.  However, some things were counted twice.  The elements that were counted twice are precisely those in <math> {}A_1\cap A_2 </math>.  Thus, we have that:
 
To find the union, we can add <math>|A_1|</math> and <math>|A_2|</math>.  In doing so, we know we have counted everything in <math>|A_1\cup A_2|</math> at least once.  However, some things were counted twice.  The elements that were counted twice are precisely those in <math> {}A_1\cap A_2 </math>.  Thus, we have that:
Line 10: Line 10:
  
 
=== Three Set Example ===
 
=== Three Set Example ===
−
Assume we are given the sizes of three sets, <math>|A_1|, |A_2|,{}</math> and <math>|A_3|</math>, the size of their pairwise intersections, <math>|A_1\cap A_2|, |A_2\cap A_3|</math> and <math>|A_3\cap A_1|</math>, and the size their overall intersection, <math>|A_1\cap A_2\cap A_3|</math>.  We wish to find the size of their union, <math>|A_1\cup A_2\cup A_3|</math>.
+
Assume we are given the sizes of three sets, <math>|A_1|, |A_2|,{}</math> and <math>|A_3|</math>, the size of their pairwise intersections, <math>|A_1\cap A_2|, |A_2\cap A_3|</math>, and <math>|A_3\cap A_1|</math>, and the size their overall intersection, <math>|A_1\cap A_2\cap A_3|</math>.  We wish to find the size of their union, <math>|A_1\cup A_2\cup A_3|</math>.
  
 
Just like in the Two Set Example, we start with the sum of the sizes of the individual sets <math>|A_1|+|A_2|+|A_3|</math>.  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 <math>|A_1\cap A_2|+|A_2\cap A_3| + |A_3\cap A_1|</math>.  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 <math>|A_1\cap A_2\cap A_3|</math>.  Putting this all together gives:
 
Just like in the Two Set Example, we start with the sum of the sizes of the individual sets <math>|A_1|+|A_2|+|A_3|</math>.  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 <math>|A_1\cap A_2|+|A_2\cap A_3| + |A_3\cap A_1|</math>.  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 <math>|A_1\cap A_2\cap A_3|</math>.  Putting this all together gives:
Line 20: Line 20:
 
Problem:
 
Problem:
  
−
There are five courses at my school.
+
There are five courses at my school. Students take the classes as follows.
 
243 take algebra.
 
243 take algebra.
 
323 take language arts.
 
323 take language arts.
Line 31: Line 31:
 
121 take algebra and history.
 
121 take algebra and history.
 
111 take language arts and social studies.
 
111 take language arts and social studies.
−
90 take language atrts and biology.
+
90 take language arts and biology.
 
80 take language arts and history.
 
80 take language arts and history.
 
60 take social studies and biology.
 
60 take social studies and biology.
 
70 take social studies and history.
 
70 take social studies and history.
 
60 take biology and history.
 
60 take biology and history.
−
50 take algebra, language arts and social studies.
+
50 take algebra, language arts, and social studies.
−
50 take algebra, language arts and biology.
+
50 take algebra, language arts, and biology.
−
50 take algebra, language arts and history.
+
50 take algebra, language arts, and history.
−
50 take algebra, social studies and biology.
+
50 take algebra, social studies, and biology.
−
50 take algebra, social studies and history.
+
50 take algebra, social studies, and history.
−
50 take algebra, biology and history.
+
50 take algebra, biology, and history.
−
50 take language arts, social studies and biology.
+
50 take language arts, social studies, and biology.
−
50 take language arts, social studies and history.
+
50 take language arts, social studies, and history.
−
50 take language arts, biology and history.
+
50 take language arts, biology, and history.
−
50 take social studies, biology and history.
+
50 take social studies, biology, and history.
−
20 take algebra, language arts, social studies and biology.
+
20 take algebra, language arts, social studies, and biology.
−
15 take algebra, language arts, social studies and history.
+
15 take algebra, language arts, social studies, and history.
−
15 take algebra, language arts, biology and history.
+
15 take algebra, language arts, biology, and history.
−
10 take algebra, social studies, biology and history.
+
10 take algebra, social studies, biology, and history.
−
10 take language arts, social studies, biology and history.
+
10 take language arts, social studies, biology, and history.
−
5 take all three.
+
5 take all five.
 
None take none.  
 
None take none.  
  
Line 58: Line 58:
  
 
Solution:
 
Solution:
−
Let A be the subset of students who take algebra, L-languages,S-social s.,B-biology,H-history, M the set of all students.We have:
+
Let A be the subset of students who take algebra, L-languages, S-social s., B-biology, H-history, M the set of all students.We have:
  
 
<math>
 
<math>

Revision as of 12:19, 3 July 2006

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, $|A_1|$ and $|A_2|$, and the size of their intersection, $|A_1\cap A_2|$. We wish to find the size of their union, $|A_1\cup A_2|$.

To find the union, we can add $|A_1|$ and $|A_2|$. In doing so, we know we have counted everything in $|A_1\cup A_2|$ at least once. However, some things were counted twice. The elements that were counted twice are precisely those in ${}A_1\cap A_2$. Thus, we have that:

$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1\cap A_2|.$

Three Set Example

Assume we are given the sizes of three sets, $|A_1|, |A_2|,{}$ and $|A_3|$, the size of their pairwise intersections, $|A_1\cap A_2|, |A_2\cap A_3|$, and $|A_3\cap A_1|$, and the size their overall intersection, $|A_1\cap A_2\cap A_3|$. We wish to find the size of their union, $|A_1\cup A_2\cup A_3|$.

Just like in the Two Set Example, we start with the sum of the sizes of the individual sets $|A_1|+|A_2|+|A_3|$. 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 $|A_1\cap A_2|+|A_2\cap A_3| + |A_3\cap A_1|$. 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 $|A_1\cap A_2\cap A_3|$. Putting this all together gives:

$|A_1\cup A_2\cup A_3| = |A_1| + |A_2| + |A_3| -|A_1\cap A_2| - |A_2\cap A_3| - |A_3\cap A_1| +|A_1\cap A_2\cap A_3|.$


Five Set Example

Problem:

There are five courses at my school. Students take the classes as follows. 243 take algebra. 323 take language arts. 143 take scocial studies. 241 take biology. 300 take history. 213 take algebra and language arts. 264 take algebra and social studies. 144 take algebra and biology. 121 take algebra and history. 111 take language arts and social studies. 90 take language arts and biology. 80 take language arts and history. 60 take social studies and biology. 70 take social studies and history. 60 take biology and history. 50 take algebra, language arts, and social studies. 50 take algebra, language arts, and biology. 50 take algebra, language arts, and history. 50 take algebra, social studies, and biology. 50 take algebra, social studies, and history. 50 take algebra, biology, and history. 50 take language arts, social studies, and biology. 50 take language arts, social studies, and history. 50 take language arts, biology, and history. 50 take social studies, biology, and history. 20 take algebra, language arts, social studies, and biology. 15 take algebra, language arts, social studies, and history. 15 take algebra, language arts, biology, and history. 10 take algebra, social studies, biology, and history. 10 take language arts, social studies, biology, and history. 5 take all five. None take none.

How many people are in my school?


Solution: Let A be the subset of students who take algebra, L-languages, S-social s., B-biology, H-history, M the set of all students.We have:

$\mid M\mid =\mid A\mid+\mid L\mid+\mid S\mid+\mid B\mid+\mid H\mid-\mid A\cap L\mid-\mid A\cap S\mid-\mid A\cap B\mid-\mid A\cap H\mid-\mid L\cap S\mid-\mid L\cap B \mid-\mid L\cap H\mid-\mid S\cap B\mid-\mid S\cap$

$H\mid-\mid B\cap H\mid+\mid A\cap L\cap S\mid+\mid A\cap L\cap B\mid+\mid A\cap L\cap H\mid+\mid A\cap S\cap B\mid+\mid A\cap S\cap H\mid+\mid A\cap B\cap H\mid+\mid L\cap S\mid H\mid+\mid L\cap S \cap B\mid+\mid S\cap B\cap$

$H\mid+\mid L \cap B\cap H\mid-\mid A\cap L\cap S\cap B\mid-\mid A\cap L\cap S\cap H\mid-\mid A\cap L\cap B\cap H\mid-\mid A\cap S\cap B\cap H\mid-\mid L\cap S\cap B\cap H\mid =$

$\displaystyle 243+323+143+241+300-213-264-144-121-111-90-80-60-70-60+50+50+50+50+50+50+50+50+50+50-20-15-15-10-10+5=472$


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 \left|A_1\cap\cdots\cap A_n\right|{}.$

Remark

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=5884"