# 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
7 years, 4 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

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!

- 7 years, 2 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

- 7 years ago

why is the intersections of A,B,C added at the end?

- 6 years, 12 months ago

To compensate for overcounting.

- 6 years ago

There are 4 bins and 20 distinct balls. What is the probability that there is at least one bin that is empty?

- 6 years, 10 months ago

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

- 6 years, 9 months ago