$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 5.1: The Size of a Union of Sets

• • Contributed by Kenneth P. Bogart
• Professor (Mathematics) at Dartmouth University

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

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

## 5.1.1 Unions of two or three sets

◦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? + 226. Give a formula for the size of the union A ∪ B of two sets A and B in terms of the sizes |A| of A, |B| of B, and |A ∩ B| of A ∩ B. If A and B are subsets of some “universal” set U, express the size of the complement U − (A ∪ B) in terms of the sizes |U| of U, |A| of A, |B| of B, and |A ∩ B| of A ∩ B. Online hint. ◦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? •228. Give a formula for the size of A ∪ B ∪ A3 in terms of the sizes of A, B, C and the intersections of these sets. Online hint.

## 5.1.2 Unions of an arbitrary number of sets

•229. Conjecture a formula for the size of a union of sets A1 ∪ A2 ∪ · · · ∪ An = [n i=1 Ai in terms of the sizes of the sets Ai 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. We will describe some notation that will make your task easier. It is similar to the notation EP (S) = X s:s∈S P(s). that we used to stand for the sum of the pictures of the elements of a set S when we introduced picture enumerators. Let us define \ i:i∈I Ai to mean the intersection over all elements i in the set I of Ai . Thus \ i:i∈{1,3,4,6} Ai = A1 ∩ A3 ∩ A4 ∩ A6. (5.1) 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 X

$I:I⊆{1,2,3,4}, |I|=2 | ∩i∈I Ai | = |A1 ∩ A2| + |A1 ∩ A3| + |A1 ∩ A4| + |A2 ∩ A3| + |A2 ∩ A4| + |A3 ∩ A4|.(5.2)$

•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. (The author’s version doesn’t use all those elements.) •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: 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, 4, and 5.) Online hint. (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.

## 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 inductive proof that relies on the fact that A1 ∪ A2 ∪ · · · ∪ An = (A1 ∪ A2 ∪ · · · ∪ An−1) ∪ An and the formula for the size of a union of two sets.

232. Give a proof of your formula for the principle of inclusion and exclusion. Online hint. A second online hint. 233. We get a more elegant proof if we ask for a picture enumerator for A1 ∪ A2 ∪ · · · ∪ An. So let us assume A is a set with a picture function P defined on it and that each set Ai is a subset of A.

1. (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 a notation like EP ( \ i:i∈S Ai) for the picture enumerator of the intersection of the sets Ai for i in a subset S of [n].
2. (b) If x ∈ [n i=1 Ai , what is the coefficient of P(x) in (the inclusionexclusion side of) your formula for EP ( [n i=1 Ai)? Online hint. A second online hint.
3. (c) If x 6∈ [n i=1 Ai , what is the coefficient of P(x) in (the inclusionexclusion side of) your formula for EP ( [n i=1 Ai)?
4. (d) How have you proved your conjecture for the picture enumerator of the union of the sets Ai?
5. (e) How can you get the formula for the principle of inclusion and exclusion from your formula for the picture enumerator of the union?

234. Frequently when we apply the principle of inclusion and exclusion, we will have a situation like that of Problem 231d. That is, we will have a set A and subsets A1, A2, . . . , An 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 Ais in A, and is denoted by A − Sn i=1 Ai , or if A is clear from context, by Sn i=1 Ai . Give the formula for Sn i=1 Ai . 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 \ i:i∈∅ Ai = A. For this reason, if we have a family of subsets Ai of a set A, we define1 \ i:i∈∅ Ai = A.