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
If there are three sets, the principle of inclusion and exclusion states
We can verify these statements for ourselves by considering the Venn Diagram of events.
More generally, if are finite sets, then the principle of inclusion and exclusion states
1. How many integers from 1 to 100 are multiples of 2 or 3?
Solution: Let be the set of integers from 1 to 100 that are multiples of 2 . Let be the set of integers from 1 to 100 that are multiples of 3 . Now, is the set of integers from 1 to 100 that are multiples of both 2 and 3, hence are multiples of 6 . By PIE,
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 symbols, the statement is still true. For example, in two variables, . The same proof using Venn diagrams works to show that each element is included once. As such, the sum of elements in is equal to the sum of elements in plus the sum of elements in minus the sum of elements in . Letting be the set of multiples of 2, and be the set of multiples of 3, then is the set of multiples of 6, hence the sum of is
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 denote the set of ways to distribute gifts such that everyone receives a gift, possibly their own. Let denote the set of ways to distribute gifts such that person receives his or her own gift. Then we would like to find
Since is the set of ways for person 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,
Since is the set of ways person and person 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,
By continuing this argument, if people receive their own gifts, then there are possible ways. Applying PIE, we obtain
Note: A derangement of 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 , and this calculation shows .
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 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 . Let be the set of ways such that the tetrahedron box has no balls, be the set of ways such that the cube box has no balls and be the set of ways such that the dodecahedron box has no balls. We would like to find
We have , since the balls can be placed into one of the two other boxes, and , since all the balls must be placed in the remaining box, and . Hence, PIE implies