Skip to main content

Section 2.1 The Principle of Inclusion and Exclusion: the Size of a Union

One of our very first counting principles was the sum principle which says that the size of a union of disjoint sets is the sum of their sizes. Computing the size of overlapping sets requires, quite naturally, information about how they overlap. Taking such information into account will allow us to develop a powerful extension of the sum principle known as the “principle of inclusion and exclusion.”

Subsection 2.1.1 Unions of two or three sets

Activity 132.

In a biology lab study of the effects of basic fertilizer ingredients on plants, 16 plants are treated with potash, 16 plants are treated with phosphate, and among these plants, eight are treated with both phosphate and potash. No other treatments are used. How many plants receive at least one treatment? If 32 plants are studied, how many receive no treatment?

Activity 133.

Give a formula for the size of the union \(A\cup B\) of two sets \(A\) in terms of the sizes \(|A|\) of \(A\text{,}\) \(|B|\) of \(B\text{,}\) and \(|A\cap B|\) of \(A\cap B\text{.}\) If \(A\) and \(B\) are subsets of some “universal” set \(U\text{,}\) express the size of the complement \(U-(A\cup B)\) in terms of the sizes \(|U|\) of \(U\text{,}\) \(|A|\) of \(A\text{,}\) \(|B|\) of \(B\text{,}\) and \(|A\cap B|\) of \(A\cap B\text{.}\)

Hint

Try drawing a Venn Diagram.

Activity 134.

In Activity 132, there were just two fertilizers used to treat the sample plants. Now suppose there are three fertilizer treatments, and 15 plants are treated with nitrates, 16 with potash, 16 with phosphate, 7 with nitrate and potash, 9 with nitrate and phosphate, 8 with potash and phosphate and 4 with all three. Now how many plants have been treated? If 32 plants were studied, how many received no treatment at all?

Activity 135.

A formula for the size of \(A\cup B\cup C\) in terms of the sizes of \(A\text{,}\) \(B\text{,}\) \(C\) and the intersections of these sets is

\begin{equation*} |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|- |A\cap C| - |B\cap C| +|A\cap B\cap C|\text{.} \end{equation*}

Explain why this is correct using a Venn diagram. In particular, how many times are elements are in \(A \cap B \cap C\) counted? What about the other regions of the Venn diagram?

Subsection 2.1.2 Unions of an arbitrary number of sets

Activity 136.

Conjecture a formula for the size of a union of sets

\begin{equation*} A_1\cup A_2\cup \cdots\cup A_n = \bigcup_{i=1}^n A_i \end{equation*}

in terms of the sizes of the sets \(A_i\) and their intersections.

The difficulty of generalizing Activity 135 and Activity 136 is not likely to be one of being able to see what the right conjecture is, but of finding a good notation to express your conjecture. In fact, it would be easier for some people to express the conjecture in words than to express it in a notation. Here is some notation that will make your task easier. Let us define

\begin{equation*} \bigcap_{i:i\in I}A_i \end{equation*}

to mean the intersection over all elements \(i\) in the set \(I\) of \(A_i\text{.}\) Thus

\begin{equation} \bigcap_{i:i\in \{1,3,4,6\}} = A_1\cap A_3\cap A_4 \cap A_6.\label{intersectionnotation}\tag{2.1} \end{equation}

This kind of notation, consisting of an operator with a description underneath of the values of a dummy variable of interest to us, can be extended in many ways. For example

\begin{align} \sum_{I:I \subseteq \{1,2,3,4\}, \ |I|=2} |\cap_{i\in I} A_i| \amp = |A_1\cap A_2|+ |A_1\cap A_3| +|A_1\cap A_4|\notag\\ \amp + |A_2\cap A_3|+ |A_2\cap A_4| +|A_3\cap A_4|.\label{notationsolution}\tag{2.2} \end{align}
Exercise 137.

Use notation something like that of Equation (2.1) and Equation (2.2) to express the answer to Activity 136. Note there are many different correct ways to do this problem. Try to write down more than one and choose the nicest one you can. Say why you chose it (because your view of what makes a formula nice may be different from somebody else's). The nicest formula won't necessarily involve all the elements of Equations (2.1) and (2.2).

Whether we try to write down a nice expression for the size of a union or whether we just have the basic idea, we should now be able to answer counting questions like the following. We will return to this sort of problem in more detail later, but the adventurous reader can attempt it here.

Exercise 138.

A group of \(n\) students goes to a restaurant carrying backpacks. The manager invites everyone to check their backpack at the check desk and everyone does. While they are eating, a child playing in the check room randomly moves around the claim check stubs on the backpacks. We will try to compute the probability that, at the end of the meal, at least one student receives his or her own backpack. This probability is the fraction of the total number of ways to return the backpacks in which at least one student gets his or her own backpack back.

(a)

What is the total number of ways to pass back the backpacks?

(b)

In how many of the distributions of backpacks to students does at least one student get his or her own backpack?

Hint 1

For each student, how big is the set of backpack distributions in which that student gets the correct backpack? It might be a good idea to first consider cases with \(n=3\text{,}\) \(4\text{,}\) and \(5\text{.}\)

Hint 2

For each pair of students (say Mary and Jim, for example) how big is the set of backpack distributions in which the students in this pair get the correct backpack. What does the question have to do with unions or intersections of sets. Keep on increasing the number of students for which you ask this kind of question.

(c)

What is the probability that at least one student gets the correct backpack?

(d)

What is the probability that no student gets his or her own backpack?

(e)

As the number of students becomes large, what does the probability that no student gets the correct backpack approach?

Exercise 138 is “classically” called the hatcheck problem; the name comes from substituting hats for backpacks. If is also sometimes called the derangement problem. A derangement of an \(n\)-element set is a permutation of that set (thought of as a bijection) that maps no element of the set to itself. One can think of a way of handing back the backpacks as a permutation \(f\) of the students: \(f(i)\) is the owner of the backpack that student \(i\) receives. Then a derangement is a way to pass back the backpacks so that no student gets his or her own.

Subsection 2.1.3 The Principle of Inclusion and Exclusion

The formula you have given in Exercise 137 is often called the principle of inclusion and exclusion for unions of sets. The reason is the pattern in which the formula first adds (includes) all the sizes of the sets, then subtracts (excludes) all the sizes of the intersections of two sets, then adds (includes) all the sizes of the intersections of three sets, and so on. Notice that we haven't yet proved the principle. There are a variety of proofs. Perhaps one of the most straightforward (though not the most elegant) is an inductive proof that relies on the fact that

\begin{equation*} A_1 \cup A_2 \cup \cdots \cup A_n = \left(A_1 \cup A_2 \cup \cdots \cup A_{n-1}\right) \cup A_n \end{equation*}

and the formula for the size of a union of two sets: \(\card{A \cup B} = \card{A} + \card{B} - \card{A\cap B}\text{.}\)

Exercise 139.

Give a proof of your formula for the principle of inclusion and exclusion.

Hint 1

Try induction.

Hint 2

We can apply the formula of Activity 133 to get

\begin{align*} \left|\bigcup_{i=1}^n A_i \right| \amp = \left|\left(\bigcup_{i=1}^{n-1} A_i\right) \cup A_n \right| \\ \amp = \left| \bigcup_{i=1}^{n-1} A_i\right| + |A_n| - \left|\left( \bigcup_{i=1}^{n-1} A_i\right) \cap A_n\right|\\ \amp = \left| \bigcup_{i=1}^{n-1} A_i\right| + |A_n| - \left|\bigcup_{i=1}^{n-1} A_i \cap A_n\right| \end{align*}

Frequently when we apply the principle of inclusion and exclusion, we will have a situation like that of part (d) of Task 138.d. That is, we will have a set \(A\) and subsets \(A_1, A_2, \ldots, A_n\) and we will want the size or the probability of the set of elements in \(A\) that are not in the union. This set is known as the complement of the union of the \(A_i\)s in \(A\text{,}\) and is denoted by \(A \setminus \bigcup_{i=1}^n A_i\text{,}\) or if \(A\) is clear from context, by \(\overline{\bigcup_{i=1}^n A_i}\text{.}\)

Since all the \(A_i\)s are subsets of \(A\text{,}\) one way to write this size is as \(|A| - \sum_{S:S \subseteq [n], S \ne \emptyset}(-1)^{|S|-1} |\bigcap_{i:i \in S}A_i|\text{.}\) Letting \(|A| = \left|\bigcap_{i:i \in \emptyset} A_i\right|\text{,}\) we may write \(\left|\overline{\bigcup_{i=1}^n A_i}\right| = \sum_{S:S \subseteq [n]} (-1)^{|S|}\left| \bigcap_{i:i\in S} A_i\right|\text{.}\)

The principle of inclusion and exclusion generally refers to both this formula and the one for the union. Both formulas are notationally horrific, but the idea is straight forward. To find the size of the union, we add the sizes of each set individually, then subtract each of the sizes of the intersections of pairs of sets, then add back in the sizes of the intersections of triples of sets, subtract 4-tuple intersections, add 5-tuple intersections, and so on until we are done. The compliment can be calculated by subtracting the union from the size of the original set.

Subsection 2.1.4 Application of Inclusion and Exclusion

Multisets with restricted numbers of elements.
Exercise 140.

In how many ways may we distribute \(k\) identical apples to \(n\) children so that no child gets more than four apples?

Hint

Notice that it is straightforward to figure out how many ways we may pass out the apples so that child \(i\) gets five or more apples: give five apples to child \(i\) and then pass out the remaining apples however you choose. And if we want to figure out how many ways we may pass out the apples so that a given set \(C\) of children each get five or more apples, we give five to each child in \(C\) and then pass out the remaining \(k-5|C|\) apples however we choose.

The Menage Problem.
Exercise 141.

A group of \(n\) married couples comes to a group discussion session where they all sit around a round table. In how many ways can they sit so that no person is next to his or her spouse? (Note that two people of the same sex can sit next to each other.)

Hint 1

Start with two questions that can apply to any inclusion-exclusion problem. Do you think you would be better off trying to compute the size of a union of sets or the size of a complement of a union of sets? What kinds of sets (that are conceivably of use to you) is it easy to compute the size of? (The second question can be interpreted in different ways, and for each way of interpreting it, the answer may help you see something you can use in solving the problem.)

Hint 2

Suppose we have a set \(S\) of couples whom we want to seat side by side. We can think of lining up \(|S|\) couples and \(2n - 2|S|\) individual people in a circle. In how many ways can we arrange this many items in a circle?

Exercise 142.

A group of \(n\) married couples comes to a group discussion session where they all sit around a round table. In how many ways can they sit so that no person is next to his or her spouse or a person of the same sex? This problem is called the menage problem.

Hint 1

Reason somewhat as you did in Exercise 141, noting that if the set of couples who do sit side-by-side is nonempty, then the sex of the person at each place at the table is determined once we seat one couple in that set.

Hint 2

Think in terms of the sets \(A_i\) of arrangements of people in which couple \(i\) sits side-by-side. What does the union of the sets \(A_i\) have to do with the problem?

Counting Derangements.

A derangement of \(n\) elements \(\{1,2,3,\ldots, n\}\) is a permutation in which no element is fixed. For example, there are \(6\) permutations of the three elements \(\{1,2,3\}\text{:}\)

\begin{equation*} 123 ~~ 132 ~~ 213 ~~ 231 ~~ 312 ~~ 321. \end{equation*}

but most of these have one or more elements fixed: \(123\) has all three elements fixed since all three elements are in their original positions, \(132\) has the first element fixed (1 is in its original first position), and so on. In fact, the only derangements of three elements are

\begin{equation*} 231 \text{ and } 312. \end{equation*}

If we go up to 4 elements, there are \(4! = 24\) permutations. How many of these are derangements? If you list out all 24 permutations and eliminate those which are not derangements, you will be left with just 9 derangements. Let's see how we can get that number using PIE.

Activity 143.
(a)

Write out all 24 permutations of \([4]\) and circle the 9 that are derangements.

Hint

Note that 2341 should be circled, but 2314 should not be circled.

(b)

Locate the permutations that leave 1 fixed (so 1 is the first number in the permutation). How many are there, and does this make sense? Check there are an equal number that leave 2 fixed, and that leave 3 fixed, and that leave 4 fixed.

(c)

Notice that there are permutations that leave both 1 and 2 fixed. Which ones are these, and how many are there? Again, verify that there are just as many that leave any pair of numbers fixed.

(d)

Repeat the previous task for triples of elements fixed and for all four elements fixed.

(e)

We can use the principle of inclusion and exclusion to find the total number of derangements as follows:

\begin{equation*} d_4 = 4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4}0!\right]. \end{equation*}

Explain why this is correct. In particular, for the permutation 1234 (where everything is fixed), where in the expression above is it counted?

Of course we can use a similar formula to count the derangements of any number of elements. However, the more elements we have, the longer the formula gets. Here is another example:

Exercise 144.

Five gentlemen attend a party, leaving their hats at the door. At the end of the party, they hastily grab hats on their way out. How many different ways could this happen so that none of the gentlemen leave with their own hat?

Derangments are interesting in their own right. In Section 1.2 you proved a few results using combinatorial proofs. In particular, we established the following, which you might try to prove again here.

Here is another recursion you can explore.

Exercise 145.

Use the principle of inclusion and exclusion to derive the recursion

\begin{equation*} d_n = nd_{n-1} + (-1)^n\text{.} \end{equation*}

The non-recursive formula for derangments is messy due to the use of the principle of inclusion and exclusion. Actually, it can be cleaned up a bit, which leads to a remarkable result.

Exercise 146.
(a)

We know that \(d_3 = 3! - \left(\binom{3}{1}2! - \binom{3}{2}1! + \binom{3}{3}0! \right)\text{.}\) Use the factorial formula for \(\binom{n}{k}\) to simplify this. Factor out a \(3!\) leaving terms that are each nice unit fractions.

(b)

Generalize the previous part to give a nice clean expression for \(d_n\text{.}\)

(c)

The alternating sum of unit fractions you get might look familiar if you have thought about Taylor series from calculus recently. For large \(n\text{,}\) what fraction of all permutations are derangements?

Hint

The Taylor series for \(e^x\) is \(1+x + \frac{1}{2!}x^2 + \frac{1}{3!}x^3 + \cdots\text{.}\) What happens if you replace \(x\) with \(-1\text{?}\)

Counting surjective functions.

There are six surjective functions \(f:[3]\to [2]\text{,}\) which happens to be \(2^3 - 2\text{.}\) This makes sense because there are eight functions all together, but two are not surjective (do you see why?).

Consider functions \(f:[3]\to [3]\text{.}\) Since each element of the domain has three potential images, there are \(3^3\) such functions. If we only count the injective (one-to-one) functions, we will find \(3! = 6\text{.}\) Since the size of the domain and codomain are equal, this is also the number of surjective functions (since every injective function is surjective in this case).

However, when the size of the codomain is larger than the size of the domain, there will be no injections and plenty of surjections. To see how to count surjections in general, let's explore the case above where we know the answer already.

Activity 147.
Write out all 27 functions \(f:[3] \to [3]\text{.}\) You could use two-line notation here, but to save space, perhaps just write the bottom line. So the function that sends 1 to 1, 2 to 3 and 3 to 3 can be represented as (1,3,3).
(a)

Circle the functions you found above that are surjective. Verify that there are just 6.

(b)

There are various ways that a function might fail to be surjective. One way is for 1 to not be in the range. How many functions are there like this (identify them)? Does this number make sense? Check this is the same number of functions that do not include 2 in the range.

(c)

How many functions do not have 1 or 2 in the range? Does this number make sense as well?

(d)

Explain what all this has to do with the expression

\begin{equation*} 3^3 - \left[ \binom{3}{1}2^3 - \binom{3}{2}1^3 + \binom{3}{3}0^3\right]\text{.} \end{equation*}

Let's generalize!

Activity 148.

Given a function \(f\) from the \(k\)-element set \(K\) to the \(n\)-element set \([n]\text{,}\) we say \(f\) is in the set \(A_i\) if \(f(x)\not= i\) for any \(x\) in \(K\text{.}\)

How many of these sets does a surjective function belong to?

Use this to find the number of functions from a \(k\)-element set onto an \(n\)-element set?

Exercise 149.

If we roll a die eight times, we get a sequence of 8 numbers, the number of dots on top on the first roll, the number on the second roll, and so on.

(a)

What is the number of ways of rolling the die eight times so that each of the numbers one through six appears at least once in our sequence? To get a numerical answer, you will likely need a computer algebra package.

(b)

What is the probability that we get a sequence in which all six numbers between one and six appear? To get a numerical answer, you will likely need a computer algebra package, programmable calculator, or spreadsheet.

(c)

How many times do we have to roll the die to have probability at least one half that all six numbers appear in our sequence? To answer this question, you will likely need a computer algebra package, programmable calculator, or spreadsheet.