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.”
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?
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{.}\)
Try drawing a Venn Diagram.
In Activity 216, 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?
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.
Try drawing a Venn Diagram.
Conjecture a formula for the size of a union of sets
in terms of the sizes of the sets \(A_i\) and their intersections.
The difficulty of generalizing Activity 219 to Activity 220 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
to mean the intersection over all elements \(i\) in the set \(I\) of \(A_i\text{.}\) Thus
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
Use notation something like that of Equation (3.1) and Equation (3.2) to express the answer to Activity 220. 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 (3.1) and (3.2).
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.
What is the total number of ways to pass back the backpacks?
In how many of the distributions of backpacks to students does at least one student get his or her own backpack?
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{.}\)
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.
What is the probability that at least one student gets the correct backpack?
What is the probability that no student gets his or her own backpack?
As the number of students becomes large, what does the probability that no student gets the correct backpack approach?
Activity 222 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 formula you have given in Activity 221 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
and the formula for the size of a union of two sets.
Give a proof of your formula for the principle of inclusion and exclusion.
Try induction.
We can apply the formula of Activity 217 to get
Frequently when we apply the principle of inclusion and exclusion, we will have a situation like that of part (d) of Task 222.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 generall refers to both this formula and the one for the union.
We can find a very elegant way of writing the formula in Activity 224 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 1 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{.}\)
In how many ways may we distribute \(k\) identical apples to \(n\) children so that no child gets more than four apples?
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.
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.)
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.)
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?
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.
Reason somewhat as you did in Activity 226, 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.
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?
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{:}\)
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
If we go up to 4 elements, there are 24 permutations (because we have 4 choices for the first element, 3 choices for the second, 2 choices for the third leaving only 1 choice for the last). 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.
How many derangements are there of 4 elements?
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:
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?
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 every \(x\) in \(K\text{.}\) How many of these sets does an onto function belong to? What is the number of functions from a \(k\)-element set onto an \(n\)-element set?
Find a formula for the Stirling number (of the second kind) \(S(k,n)\text{.}\)
What does Activity 230 have to do with this question?
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.
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.
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.
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.