Principle of Inclusion and Exclusion (PIE)
The principle of inclusion and exclusion (PIE) is a counting technique that computes the number of elements that satisfy at least one of several properties while guaranteeing that elements satisfying more than one property are not counted twice.
An underlying idea behind PIE is that summing the number of elements that satisfy at least one of two categories and subtracting the overlap prevents double counting. For instance, the number of people that have at least one cat or at least one dog can be found by taking the number of people who own a cat, adding the number of people that have a dog, then subtracting the number of people who have both.
PIE is particularly useful in combinatorics and probability problem solving when it is necessary to devise a counting method that ensures an object is not counted twice.
Two Sets
In the case of objects being separated into two (possibly disjoint) sets, the principle of inclusion and exclusion states
\[ |A \cup B| = |A|+|B| - |A\cap B|,\]
where \(|S|\) denotes the cardinality, or number of elements, of set \(S\) in set notation.
To prove this statement, we will show that every element which belongs in one of these sets is counted exactly once, and every element that is not in these sets is counted exactly zero times.
Case 1. Element is not in \(A\), and not in \(B\).
It is obvious it is counted zero times in the LHS. It is obvious it is counted zero times in the RHS.Case 2. Element is in \(A\), and not in \(B\).
It will be counted once on the LHS. On the RHS, it is counted once in \( |A| \).Case 3. Element is not in \(A\), and is in \(B\).
It will be counted once on the LHS. On the RHS, it is counted once in \( |B| \).Case 4. Element is in \(A\), and in \(B\).
It will be counted once on the LHS. On the RHS, it is counted \(+1\) in \(|A|\), \(+1\) in \(|B|\) and \(-1\) in \(|A \cap B | \). Hence, it is counted exactly once.
As a Venn diagram, PIE for two sets can be depicted easily:
How many integers from 1 to 100 are multiples of 2 or 3?
Let \( A\) be the set of integers from 1 to 100 that are multiples of 2, then \(\lvert A \rvert = 50\).
Let \( B\) be the set of integers from 1 to 100 that are multiples of 3, then \(\lvert B \rvert = 33\).
Now, \( A \cap B\) is the set of integers from 1 to 100 that are multiples of both 2 and 3, and hence are multiples of 6, implying \(\vert A \cap B \rvert = 16\).Hence, by PIE, \[ | A\cup B| = |A|+|B|-|A\cap B| = 50 + 33 - 16 = 67. \ _\square\]
A local grocery store in the outback newly opened. They were offering 1 free bottle Marmite to every \(11^\text{th}\) customer and 1 free pound of kangaroo meat for every \(13^\text{th}\) customer. If there were 1000 customers that visited them on opening day, how many customers walked away with free goodies?
Three Sets and More
We've already looked at the case of 2 sets. Before we dive into the general case, let's consider having 3 sets.
If there are three sets, the principle of inclusion and exclusion states
\[ |A\cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.\]
We can verify these statements for ourselves by considering the Venn diagram of events:
There are exactly three types of students in a school: the geeks, the wannabees, and the athletes. Each student is classified into at least one of these categories. And the total number of students in the school is 1000. Suppose that the following is given:
- The total number of students who are geeks is 310.
- The total number of students who are wannabees is 650.
- The total number of students who are athletes is 440.
- The total number of students who are both geeks and wannabees is 170.
- The total number of students who are both geeks and athletes is 150.
- The total number of students who are both wannabees and athletes is 180.
What is the total number of students who fit into all 3 categories?
Let \(G,W,A\) denote the set for geeks, wannabees, and athletes, respectively. Then by the principle of inclusion and exclusion, we have
\[n( G \cup W \cup A) = n(G) + n(W) + n(A) - n(W\cap G) - n(G\cap A) - n(W\cap A) + n(G\cap W \cap A),\]
which gives us \(1000 = 310 + 650 + 440 - 170 - 150 - 180 + n(G\cap W \cap A )=900 + n(G\cap W \cap A ) \).
So the total number of students who fit into all 3 categories is 100. \(_\square\)
We defer the proof to the general case. If you are interested, you can duplicate the proof above and check that every element in \( A \cup B \cup C \) is counted exactly once on the RHS.
More generally, if \( A_1, A_2, \ldots, A_n\) are finite sets, then the principle of inclusion and exclusion states
\[ \displaystyle \left|\bigcup_{i=1}^n A_i\right| =\sum_{i=1}^n\left|A_i\right| -\sum_{1 \leq i < j \leq n}\left|A_i\cap A_j\right| +\sum_{1\leq i < j < k \leq n}\left|A_i\cap A_j\cap A_k\right| -\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.\]
At the Winter Sochi Olympics Press Conference, there are \(200\) foreign journalists. Out of them,
- \(175\) people can speak German,
- \(150\) people can speak French,
- \(180\) people can speak English, and
- \(160\) people can speak Japanese.
What is the minimum number of foreigners that can speak all the four languages?
Derangements
Main article: Derangements
There are eight guests at a secret Santa party. Each guest brings a gift and each receives another gift in return. No one is allowed to receive the gift they brought. How many ways are there to distribute the gifts?
Let \( A\) denote the set of ways to distribute gifts such that everyone receives a gift, possibly their own. Let \( A_i\) denote the set of ways to distribute gifts such that person \( i\) receives his or her own gift. Then we would like to find
\[ |A| - |A_1 \cup A_2 \cup \cdots \cup A_8|.\]
Since \( A_i\) is the set of ways for person \(i\) to receive his/her own gift, there are 7 choices of gifts for the next person, 6 choices of gifts for the following person, and so on. By the rule of product,
\[ |A_i|=7\times 6 \times \cdots \times 2 \times 1 = 7!. \]
Since \( A_i \cap A_j\) is the set of ways person \(i\) and person \(j\) both receive their own gifts, there are 6 choices of gifts for the next person, 5 choices of gifts for the following person, and so on. Again by the rule of product,
\[ |A_i \cap A_j| = 6 \times 5 \times \cdots \times 2 \times 1 = 6!.\]
By continuing this argument, if \( k\) people receive their own gifts, then there are \( (8-k)!\) possible ways. Applying PIE, we obtain
\[ |A| - |A_1 \cup A_2 \cup \cdots \cup A_8| = 8! - {8 \choose 1} \times 7! + {8\choose 2} \times 6! - \cdots + {8 \choose 8} \times 0! = 14833.\ _\square\]
Note: A derangement of \( n\) objects is a permutation of the objects such that none of them stays in the same place. The number of ways this can be done is denoted \( D_n\), and this calculation shows \( D_8 = 14833\).
Problem Solving
What is the sum of all integers from 1 to 100 that are multiples of 2 or 3?
While PIE is often used to count the elements of a set, if we remove the \( | \cdot |\) symbols, the statement is still true. For example, in two variables, \( A \cup B = A + B - A \cap B \). The same proof using Venn diagrams works to show that each element is included once. As such, the sum of elements in \( A \cup B\) is equal to the sum of elements in \( A\) plus the sum of elements in \( B\) minus the sum of elements in \( A\cap B\). Let \( A\) be the set of multiples of 2 and \( B\) be the set of multiples of 3, then \( A \cap B\) is the set of multiples of 6, and hence the sum of \( A \cup B\) is
\[ \frac {(2+100)\times 50}{2} + \frac {(3 +99)\times 33}{2} - \frac {(6+96)\times 16}{2} = 3417. \ _\square \]
We have 7 balls each of different colors (red, orange, yellow, green, blue, indigo, violet) and 3 boxes each of different shapes (tetrahedron, cube, dodecahedron). How many ways are there to place these 7 balls into the 3 boxes such that each box contains at least 1 ball?
Let \( X\) be the total number of ways we can distribute the balls if there are no restrictions. Each ball can be placed into any one of the 3 boxes, so \( |X|=3^7\). Let \( T\) be the set of ways such that the tetrahedron box has no balls, \( C\) the set of ways such that the cube box has no balls, and \( D\) the set of ways such that the dodecahedron box has no balls. We would like to find
\[ |X| - |T \cup C \cup D|.\]
We have \( |T| = |C| = |D| = 2^7\), since the balls can be placed into one of the two other boxes, and \( |T\cap C | = |C \cap D| = |D \cap T| = 1^7\), since all the balls must be placed in the remaining box, and \( |T\cap C \cap D| = 0\). Hence, PIE implies
\[ |X| - |T \cup C \cup D| = 3^7 - 3 \times 2^7 + 3 \times 1^7 - 0 = 1806. \ _\square\]
At a construction site, Jorge is in charge of hiring skilled workers for the project. Out of 80 candidates that he interviewed, he found that
- 45 were painters,
- 50 were electricians,
- 50 were plumbers,
- 15 had skills in all three areas, and
- all of them had skills in at least one of these areas.
If he hired everyone who was skilled in exactly 2 areas, how many candidates were hired?