CTGD The size of a union of sets

Section 5.1 The size of a union of sets

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 5.1.1 Unions of two or three sets

Problem 225

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?

Problem 226

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.

Problem 227

In Problem 225, 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?

Problem 228

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

Hint

Try drawing a Venn Diagram.

Subsection 5.1.2 Unions of an arbitrary number of sets

Problem 229

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 Problem 228 to Problem 229 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{5.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{5.2} \end{align}

Problem 230

Use notation something like that of Equation (5.1) and Equation (5.2) to express the answer to Problem 229. 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 (5.1) and (5.2).

Problem 231

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?

Problem 231 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 5.1.3 The Principle of Inclusion and Exclusion

The formula you have given in Problem 230 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 iductive 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.

Problem 232

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 Problem 226 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*}

Problem 233

We get a more elegant proof if we ask for a picture enumerator for \(A_1 \cup A_2 \cup \cdots \cup A_n\text{.}\) so let us assume \(A\) is a set with a picture function \(P\) defined on it and that each set \(A_i\) is a subset of \(A\text{.}\)

(a)

By thinking about how we got the formula for the size of a union, write down instead a conjecture for the picture enumerator of a union. You could use notation like \(E_P(\bigcap_{i:i\in S} A_i)\) for the picture enumerator of the intersection of the sets \(A_i\) for \(i\) in a subset of \(S\) of \([n]\text{.}\)

(b)

If \(x \in \bigcup_{i=1}^n A_i\text{,}\) what is the coefficient for \(P(x)\) in (the inclusion-exclusion side of) your formula for \(E_P(\bigcup_{i=1}^n A_i)\text{?}\)

Hint 1

Let \(T\) be the set of all \(i\) such that \(x \in A_i\text{.}\) In terms of \(x\text{,}\) what is different about the \(i\) in \(T\) and those not in \(T\text{?}\)

Hint 2

You may come to a point where the binomial theorem would be helpful.

(c)

If \(x \notin \bigcup_{i=1}^n A_i\text{,}\) what is the coefficient of \(P(x)\) in (the inclusion-exclusion side of) your formula for \(E_P(\bigcup_{i=1}^n A_i)\text{?}\)

(d)

How have you proved your conjecture for the picture enumerator of the union of the sets \(A_i\text{?}\)

(e)

How can you get the formula for the principle of inclusion and exclusion from your formula for the picture enumerator of the union?

Problem 234

Frequently when we apply the principle of inclusion and exclusion, we will have a situation like that of part (d) of Problem 231.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{.}\) Give the fomula for \(\overline{\bigcup_{i=1}^n A_i}\text{.}\) The principle of inclusion and exclusion generally refers to both this formula and the one for the union.

We can find a very elegant way of writing the formula in Problem 234 if we let \(\bigcap_{i:i\in\emptyset}A_i = A\text{.}\) for this reason, if we have a family of subsets \(A_i\) of a set \(A\text{,}\) we define¹For those interested in logic and set theory, given a family of subsets \(A_i\) of a set \(A\text{,}\) we define \(\bigcap_{i:i\in S}A_i\) to be the set of all members \(x\) of \(A\) that are in \(A_i\) for all \(i \in S\text{.}\) (Note that this allows \(x\) to be in some other \(A_j\)s as well.) Then if \(S = \emptyset\text{,}\) our intersection consists of all members \(x\) of \(A\) that satisfy the statement “if \(i\in \emptyset\text{,}\) then \(x \in A_i\text{.}\)” But since the hypothesis of the “if-then” statement is false, the statement itself is true for all \(x \in A\text{.}\) Therefor \(\bigcap_{i:i \in \emptyset}A_i = A\text{.}\) \(\bigcap_{i:i\in\emptyset}A_i = A\text{.}\)