×

This note has been used to help create the Principle of Inclusion and Exclusion (PIE) wiki

The Principle of Inclusion and Exclusion (PIE) is a way to calculate the number of elements that satisfy at least one of several given properties. If there are two sets, the principle of inclusion and exclusion states

$|A \cup B| = |A|+|B| - |A\cap B|.$

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.

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|.$

Worked Examples

1. How many integers from 1 to 100 are multiples of 2 or 3?

Solution: Let $$A$$ be the set of integers from 1 to 100 that are multiples of 2 $$( \lvert A \rvert = 50)$$. Let $$B$$ be the set of integers from 1 to 100 that are multiples of 3 $$( \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, hence are multiples of 6 $$( \vert A \cap B \rvert = 16 )$$. By PIE, $| A\cup B| = |A|+|B|-|A\cap B| = 50 + 33 - 16 = 67.$

2. What is the sum of all integers from 1 to 100 that are multiples of 2 or 3?

Solution: 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 \cup 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$$. Letting $$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, 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.$

3. [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 \ldots \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 \ldots \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 4 \times \ldots \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 \ldots \cup A_8| = 8! - {8 \choose 1} \times 7! + {8\choose 2} \times 6! - \ldots + {8 \choose 8} \times 1! = 14833.$

Note: A derangement of $$n$$ objects is a permutation of the objects such that none of them stay in the same place. The number of ways this can be done is denoted $$D_n$$, and this calculation shows $$D_8 = 14833$$.

4. 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?

Solution: Let $$X$$ be the total number of ways we can distribute the balls if there are no restriction. 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$$ be the set of ways such that the cube box has no balls and $$D$$ be 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.$

Note by Arron Kau
2 years, 12 months ago

Sort by:

And we write the number of derangements in a closed form as: $$D_n = \displaystyle n! \displaystyle (1 - \displaystyle \frac{1}{1!} + \displaystyle \frac{1}{2!} - \cdots \displaystyle (-1)^n \frac{1}{n!})$$. Nice post! · 2 years, 9 months ago

in part 3 Derangements, applying PIE we obtain ...is there something not right with the signs after you open up the bracket? · 2 years, 5 months ago

There are 4 bins and 20 distinct balls. What is the probability that there is at least one bin that is empty? · 2 years, 5 months ago

why is the intersections of A,B,C added at the end? · 2 years, 7 months ago

To compensate for overcounting. · 1 year, 8 months ago

Question-4 is Wrong.............Ans is 15............. a+b+c=7 a+1+b+1+c+1=7 a+b+c=4 so,6C2=15 · 2 years, 7 months ago

×