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|.\]

## 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

derangementof \( 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.\]

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

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

Log in to reply

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

Log in to reply

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

Log in to reply

To compensate for overcounting.

Log in to reply

Question-4 is Wrong.............Ans is 15............. a+b+c=7 a+1+b+1+c+1=7 a+b+c=4 so,

6C2=15Log in to reply

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!

Log in to reply