Investigate!11
You have 11 identical mini key-lime pies to give to 4 children. However, you don't want any kid to get more than 3 pies. How many ways can you distribute the pies?
How many ways are there to distribute the pies without any restriction?
Let's get rid of the ways that one or more kid gets too many pies. How many ways are there to distribute the pies if Al gets too many pies? What if Bruce gets too many? Or Cat? Or Dent?
What if two kids get too many pies? How many ways can this happen? Does it matter which two kids you pick to overfeed?
Is it possible that three kids get too many pies? If so, how many ways can this happen?
How should you combine all the numbers you found above to answer the original question?
Suppose now you have 13 pies and 7 children. No child can have more than 2 pies. How many ways can you distribute the pies?
Stars and bars allows us to count the number of ways to distribute 10 cookies to 3 kids and natural number solutions to \(x+y+z = 11\text{,}\) for example. A relatively easy modification allows us to put a lower bound restriction on these problems: perhaps each kid must get at least two cookies or \(x,y,z \ge 2\text{.}\) This was done by first assigning each kid (or variable) 2 cookies (or units) and then distributing the rest using stars and bars.
What if we wanted an upper bound restriction? For example, we might insist that no kid gets more than 4 cookies or that \(x, y, z \le 4\text{.}\) It turns out this is considerably harder, but still possible. The idea is to count all the distributions and then remove those that violate the condition. In other words, we must count the number of ways to distribute 11 cookies to 3 kids in which one or more of the kids gets more than 4 cookies. For any particular kid, this is not a problem; we do this using stars and bars. But how to combine the number of ways for kid A, or B or C? We must use the PIE.
The Principle of Inclusion/Exclusion (PIE) gives a method for finding the cardinality of the union of not necessarily disjoint sets. We saw in Subsection how this works with three sets. To find how many things are in one or more of the sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\) we should just add up the number of things in each of these sets. However, if there is any overlap among the sets, those elements are counted multiple times. So we subtract the things in each intersection of a pair of sets. But doing this removes elements which are in all three sets once too often, so we need to add it back in. In terms of cardinality of sets, we have
\begin{equation*}
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A\cap B \cap C|.
\end{equation*}
Example1.6.1
Three kids, Alberto, Bernadette, and Carlos, decide to share 11 cookies. They wonder how many ways they could split the cookies up provided that none of them receive more than 4 cookies (someone receiving no cookies is for some reason acceptable to these kids).
SolutionWithout the “no more than 4” restriction, the answer would be \({13 \choose 2}\text{,}\) using 11 stars and 2 bars (separating the three kids). Now count the number of ways that one or more of the kids violates the condition, i.e., gets at least 4 cookies.
Let \(A\) be the set of outcomes in which Alberto gets more than 4 cookies. Let \(B\) be the set of outcomes in which Bernadette gets more than 4 cookies. Let \(C\) be the set of outcomes in which Carlos gets more than 4 cookies. We then are looking (for the sake of subtraction) for the size of the set \(A \cup B \cup C\text{.}\) Using PIE, we must find the sizes of \(|A|\text{,}\) \(|B|\text{,}\) \(|C|\text{,}\) \(|A\cap B|\) and so on. Here is what we find.
- \(|A| = {8 \choose 2}\text{.}\) First give Alberto 5 cookies, then distribute the remaining 6 to the three kids without restrictions, using 6 stars and 2 bars.
- \(|B| = {8 \choose 2}\text{.}\) Just like above, only now Bernadette gets 5 cookies at the start.
- \(|C| = {8 \choose 2}\text{.}\) Carlos gets 5 cookies first.
- \(|A \cap B| = {3 \choose 2}\text{.}\) Give Alberto and Bernadette 5 cookies each, leaving 1 (star) to distribute to the three kids (2 bars).
- \(|A \cap C| = {3 \choose 2}\text{.}\) Alberto and Carlos get 5 cookies first.
- \(|B \cap C| = {3 \choose 2}\text{.}\) Bernadette and Carlos get 5 cookies first.
- \(|A \cap B \cap C| = 0\text{.}\) It is not possible for all three kids to get 4 or more cookies.
Combining all of these we see
\begin{equation*}
|A \cup B \cup C| = {8 \choose 2} + {8 \choose 2} + {8 \choose 2} - {3 \choose 2} - {3 \choose 2} - {3 \choose 2} + 0 = 75.
\end{equation*}
Thus the answer to the original question is \({13 \choose 2} - 75 = 78 - 75 = 3\text{.}\) This makes sense now that we see it. The only way to ensure that no kid gets more than 4 cookies is to give two kids 4 cookies and one kid 3; there are three choices for which kid that should be. We could have found the answer much quicker through this observation, but the point of the example is to illustrate that PIE works!
For four or more sets, we do not write down a formula for PIE. Instead, we just think of the principle: add up all the elements in single sets, then subtract out things you counted twice (elements in the intersection of a pair of sets), then add back in elements you removed too often (elements in the intersection of groups of three sets), then take back out elements you added back in too often (elements in the intersection of groups of four sets), then add back in, take back out, add back in, etc. This would be very difficult if it wasn't for the fact that in these problems, all the cardinalities of the single sets are equal, as are all the cardinalities of the intersections of two sets, and that of three sets, and so on. Thus we can group all of these together and multiply by how many different combinations of 1, 2, 3, … sets there are.
Example1.6.2
How many ways can you distribute 10 cookies to 4 kids so that no kid gets more than 2 cookies?
SolutionThere are \({13 \choose 3}\) ways to distribute 10 cookies to 4 kids (using 10 stars and 3 bars). We will subtract all the outcomes in which a kid gets 3 or more cookies. How many outcomes are there like that? We can force kid A to eat 3 or more cookies by giving him 3 cookies before we start. Doing so reduces the problem to one in which we have 7 cookies to give to 4 kids without any restrictions. In that case, we have 7 stars (the 7 remaining cookies) and 3 bars (one less than the number of kids) so we can distribute the cookies in \({10 \choose 3}\) ways. Of course we could choose any one of the 4 kids to give too many cookies, so it would appear that there are \({4 \choose 1}{10 \choose 3}\) ways to distribute the cookies giving too many to one kid. But in fact, we have over counted.
We must get rid of the outcomes in which two kids have too many cookies. There are \({4 \choose 2}\) ways to select 2 kids to give extra cookies. It takes 6 cookies to do this, leaving only 4 cookies. So we have 4 stars and still 3 bars. The remaining 4 cookies can thus be distributed in \({7 \choose 3}\) ways (for each of the \({4 \choose 2}\) choices of which 2 kids to over-feed).
But now we have removed too much. We must add back in all the ways to give too many cookies to three kids. This uses 9 cookies, leaving only 1 to distribute to the 4 kids using stars and bars, which can be done in \({4 \choose 3}\) ways. We must consider this outcome for every possible choice of which three kids we over-feed, and there are \({4 \choose 3}\) ways of selecting that set of 3 kids.
Next we would subtract all the ways to give four kids too many cookies, but in this case, that number is 0.
All together we get that the number of ways to distribute 10 cookies to 4 kids without giving any kid more than 2 cookies is:
\begin{equation*}
{13 \choose 3} - \left[{4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3}\right]
\end{equation*}
which is
\begin{equation*}
286 - [480 - 210 + 16] = 0.
\end{equation*}
This makes sense: there is NO way to distribute 10 cookies to 4 kids and make sure that nobody gets more than 2. It is slightly surprising that
\begin{equation*}
{13 \choose 3} = \left[{4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3}\right]
\end{equation*}
but since PIE works, this equality must hold.
Just so you don't think that these problems always have easier solutions, consider the following example.
Example1.6.3
Earlier (Example 1.5.3) we counted the number of solutions to the equation
\begin{equation*}
x_1 + x_2 + x_3 + x_4 + x_5 = 13
\end{equation*}
where \(x_i \ge 0\) for each \(x_i\text{.}\)
How many of those solutions have \(0 \le x_i \le 3\) for each \(x_i\text{?}\)
SolutionWe must subtract off the number of solutions in which one or more of the variables has a value greater than 3. We will need to use PIE because counting the number of solutions for which each of the five variables separately are greater than 3 counts solutions multiple times. Here is what we get:
Total solutions: \({17 \choose 4}\text{.}\)
Solutions where \(x_1 > 3\text{:}\) \({13 \choose 4}\text{.}\) Give \(x_1\) 4 units first, then distribute the remaining 9 units to the 5 variables.
Solutions where \(x_1 > 3\) and \(x_2 > 3\text{:}\) \({9 \choose 4}\text{.}\) After you give 4 units to \(x_1\) and another 4 to \(x_2\text{,}\) you only have 5 units left to distribute.
Solutions where \(x_1 > 3\text{,}\) \(x_2 > 3\) and \(x_3 > 3\text{:}\) \({5 \choose 4}\text{.}\)
Solutions where \(x_1 > 3\text{,}\) \(x_2 > 3\text{,}\) \(x_3 > 3\text{,}\) and \(x_4 > 3\text{:}\) 0.
We also need to account for the fact that we could choose any of the five variables in the place of \(x_1\) above (so there will be \({5 \choose 1}\) outcomes like this), any pair of variables in the place of \(x_1\) and \(x_2\) (\({5 \choose 2}\) outcomes) and so on. It is because of this that the double counting occurs, so we need to use PIE. All together we have that the number of solutions with \(0 \le x_i \le 3\) is
\begin{equation*}
{17 \choose 4} - \left[{5\choose 1}{13 \choose 4} - {5 \choose 2}{9 \choose 4} + {5 \choose 3}{5 \choose 4}\right] = 15.
\end{equation*}
SubsectionCounting Derangements
¶
Investigate!12
For your senior prank, you decide to switch the nameplates on your favorite 5 professors' doors. So that none of them feel left out, you want to make sure that all of the nameplates end up on the wrong door. How many ways can this be accomplished?
The advanced use of PIE has applications beyond stars and bars. 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 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.
Example1.6.4
How many derangements are there of 4 elements?
SolutionWe count all permutations, and subtract those which are not derangements. There are \(4! = 24\) permutations of 4 elements. Now for a permutation to not be a derangement, at least one of the 4 elements must be fixed. There are \({4 \choose 1}\) choices for which single element we fix. Once fixed, we need to find a permutation of the other three elements. There are \(3!\) permutations on 3 elements. But now we have counted too many non-derangements, so we must subtract those permutations which fix two elements. There are \({4 \choose 2}\) choices for which two elements we fix, and then for each pair, \(2!\) permutations of the remaining elements. But this subtracts too many, so add back in permutations which fix 3 elements, all \({4 \choose 3}1!\) of them. Finally subtract the \({4 \choose 4}0!\) permutations (recall \(0! = 1\)) which fix all four elements. All together we get that the number of derangements of 4 elements is:
\begin{equation*}
4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4}0!\right] = 24 - 15 = 9.
\end{equation*}
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:
Example1.6.5
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?
SolutionWe are counting derangements on 5 elements. There are \(5!\) ways for the gentlemen to grab hats in any order—but many of these permutations will result in someone getting their own hat. So we subtract all the ways in which one or more of the men get their own hat. In other words, we subtract the non-derangements. Doing so requires PIE. Thus the answer is:
\begin{equation*}
5! - \left[{5 \choose 1}4! - {5 \choose 2}3! + {5 \choose 3}2! - {5 \choose 4}1! + {5 \choose 5}0!\right].
\end{equation*}
SubsectionCounting Functions
¶
Investigate!13
Consider all functions \(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\text{.}\) How many functions are there all together? How many of those are injective? Remember, a function is an injection if every input goes to a different output.
-
Consider all functions \(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\text{.}\) How many of the injections have the property that \(f(x) \ne x\) for any \(x \in \{1,2,3,4,5\}\text{?}\)
Your friend claims that the answer is:
\begin{equation*}
5! - \left[ {5\choose 1}4! - {5 \choose 2}3! + {5\choose 3}2! - {5 \choose 4}1! + {5\choose 5}0! \right].
\end{equation*}
Explain why this is correct.
Recall that a surjection is a function for which every element of the codomain is in the range. How many of the functions \(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\) are surjective? Use PIE!
We have seen throughout this chapter that many counting questions can be rephrased as questions about counting functions with certain properties. This is reasonable since many counting questions can be thought of as counting the number of ways to assign elements from one set to elements of another.
Example1.6.6
You decide to give away your video game collection so to better spend your time studying advance mathematics. How many ways can you do this, provided:
- You want to distribute your 3 different PS4 games among 5 friends, so that no friend gets more than one game?
- You want to distribute your 8 different 3DS games among 5 friends?
- You want to distribute your 8 different SNES games among 5 friends, so that each friend gets at least one game?
In each case, model the counting question as a function counting question.
Solution
-
We must use the three games (call them 1, 2, 3) as the domain and the 5 friends (a,b,c,d,e) as the codomain (otherwise the function would not be defined for the whole domain when a friend didn't get any game). So how many functions are there with domain \(\{1,2,3\}\) and codomain \(\{a,b,c,d,e\}\text{?}\) The answer to this is \(5^3=125\text{,}\) since we can assign any of 5 elements to be the image of 1, any of 5 elements to be the image of 2 and any of 5 elements to be the image of 3.
But this is not the correct answer to our counting problem, because one of these functions is \(f= \twoline{1\amp 2\amp 3}{a\amp a\amp a}\text{;}\) one friend can get more than one game. What we really need to do is count injective functions. This gives \(P(5,3) = 60\) functions, which is the answer to our counting question.
Again, we need to use the 8 games as the domain and the 5 friends as the codomain. We are counting all functions, so the number of ways to distribute the games is \(5^8\text{.}\)
This question is harder. Use the games as the domain and friends as the codomain (otherwise an element of the domain would have more than one image, which is impossible). To ensure that every friend gets at least one game means that every element of the codomain is in the range. In other words, we are looking for surjective functions. How do you count those??
In Example 1.1.5 we saw how to count all functions (using the multiplicative principle) and in Example 1.3.4 we learned how to count injective functions (using permutations). Surjective functions are not as easily counted (unless the size of the domain is smaller than the codomain, in which case there are none).
The idea is to count the functions which are not surjective, and then subtract that from the total number of functions. This works very well when the codomain has two elements in it:
Example1.6.7
How many functions \(f: \{1,2,3,4,5\} \to \{a,b\}\) are surjective?
SolutionThere are \(2^5\) functions all together, two choices for where to send each of the 5 elements of the domain. Now of these, the functions which are not surjective must exclude one or more elements of the codomain from the range. So first, consider functions for which \(a\) is not in the range. This can only happen one way: everything gets sent to \(b\text{.}\) Alternatively, we could exclude \(b\) from the range. Then everything gets sent to \(a\text{,}\) so there is only one function like this. These are the only ways in which a function could not be surjective (no function excludes both \(a\) and \(b\) from the range) so there are exactly \(2^5 - 2\) surjective functions.
When there are three elements in the codomain, there are now three choices for a single element to exclude from the range. Additionally, we could pick pairs of two elements to exclude from the range, and we must make sure we don't over count these. It's PIE time!
Example1.6.8
How many functions \(f: \{1,2,3,4,5\} \to \{a,b,c\}\) are surjective?
SolutionAgain start with the total number of functions: \(3^5\) (as each of the five elements of the domain can go to any of three elements of the codomain). Now we count the functions which are not surjective.
Start by excluding \(a\) from the range. Then we have two choices (\(b\) or \(c\)) for where to send each of the five elements of the domain. Thus there are \(2^5\) functions which exclude \(a\) from the range. Similarly, there are \(2^5\) functions which exclude \(b\text{,}\) and another \(2^5\) which exclude \(c\text{.}\) Now have we counted all functions which are not surjective? Yes, but in fact, we have counted some multiple times. For example, the function which sends everything to \(c\) was one of the \(2^5\) functions we counted when we excluded \(a\) from the range, and also one of the \(2^5\) functions we counted when we excluded \(b\) from the range. We must subtract out all the functions which specifically exclude two elements from the range. There is 1 function when we exclude \(a\) and \(b\) (everything goes to \(c\)), one function when we exclude \(a\) and \(c\text{,}\) and one function when we exclude \(b\) and \(c\text{.}\)
We are using PIE: to count the functions which are not surjective, we added up the functions which exclude \(a\text{,}\) \(b\text{,}\) and \(c\) separately, then subtracted the functions which exclude pairs of elements. We would then add back in the functions which exclude groups of three elements, except that there are no such functions. We find that the number of functions which are not surjective is
\begin{equation*}
2^5 + 2^5 + 2^5 - 1 - 1 - 1 + 0.
\end{equation*}
Perhaps a more descriptive way to write this is
\begin{equation*}
{3 \choose 1}2^5 - {3 \choose 2}1^5 + {3 \choose 3}0^5.
\end{equation*}
since each of the \(2^5\)'s was the result of choosing 1 of the 3 elements of the codomain to exclude from the range, each of the three \(1^5\)'s was the result of choosing 2 of the 3 elements of the codomain to exclude. Writing \(1^5\) instead of 1 makes sense too: we have 1 choice of were to send each of the 5 elements of the domain.
Now we can finally count the number of surjective functions:
\begin{equation*}
3^5 - \left[{3 \choose 1}2^5 - {3 \choose 2}1^5\right] = 150.
\end{equation*}
You might worry that to count surjective functions when the codomain is larger than 3 elements would be too tedious. We need to use PIE but with more than 3 sets the formula for PIE is very long. However, we have lucked out. As we saw in the example above, the number of functions which exclude a single element from the range is the same no matter which single element is excluded. Similarly, the number of functions which exclude a pair of elements will be the same for every pair. With larger codomains, we will see the same behavior with groups of 3, 4, and more elements excluded. So instead of adding/subtracting each of these, we can simply add or subtract all of them at once, if you know how many there are. This works just like it did in for the other types of counting questions in this section, only now the size of the various combinations of sets is a number raised to a power, as opposed to a binomial coefficient or factorial. Here's what happens with \(4\) and \(5\) elements in the codomain.
Example1.6.9
How many functions \(f: \{1,2,3,4,5\} \to \{a,b,c,d\}\) are surjective?
How many functions \(f: \{1,2,3,4,5\} \to \{a,b,c,d,e\}\) are surjective?
Solution
-
There are \(4^5\) functions all together; we will subtract the functions which are not surjective. We could exclude any one of the four elements of the codomain, and doing so will leave us with \(3^5\) functions for each excluded element. This counts too many so we subtract the functions which exclude two of the four elements of the codomain, each pair giving \(2^5\) functions. But this excludes too many, so we add back in the functions which exclude three of the four elements of the codomain, each triple giving \(1^5\) function. There are \({4 \choose 1}\) groups of functions excluding a single element, \({4 \choose 2}\) groups of functions excluding a pair of elements, and \({4 \choose 3}\) groups of functions excluding a triple of elements. This means that the number of functions which are not surjective is:
\begin{equation*}
{4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5.
\end{equation*}
We can now say that the number of functions which are surjective is:
\begin{equation*}
4^5 - \left[{4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5\right].
\end{equation*}
-
The number of surjective functions is:
\begin{equation*}
5^5 - \left[{5 \choose 1}4^5 - {5 \choose 2}3^5 + {5 \choose 3}2^5 - {5 \choose 4}1^5\right].
\end{equation*}
We took the total number of functions \(5^5\) and subtracted all that were not surjective. There were \({5 \choose 1}\) ways to select a single element from the codomain to exclude from the range, and for each there were \(4^5\) functions. But this double counts, so we use PIE and subtract functions excluding two elements from the range: there are \({5 \choose 2}\) choices for the two elements to exclude, and for each pair, \(3^5\) functions. This takes out too many functions, so we add back in functions which exclude 3 elements from the range: \({5 \choose 3}\) choices for which three to exclude, and then \(2^5\) functions for each choice of elements. Finally we take back out the 1 function which excludes 4 elements for each of the \({5 \choose 4}\) choices of 4 elements.
If you happen to calculate this number precisely, you will get 120 surjections. That happens to also be the value of \(5!\text{.}\) This might seem like an amazing coincidence until you realize that every surjective function \(f:X \to Y\) with \(\card{X} = \card{Y}\) finite must necessarily be a bijection. The number of bijections is always \(\card{X}!\) in this case. What we have here is a combinatorial proof of the following identity:
\begin{equation*}
n^n - \left[{n\choose 1}(n-1)^n - {n \choose 2}(n-2)^n + \cdots + {n \choose n-1}1^n \right] = n!.
\end{equation*}
We have seen that counting surjective functions is another nice example of the advanced use of the Principle of Inclusion/Exclusion. Also, counting injective functions turns out to be equivalent to permutations, and counting all functions has a solution akin to those counting problems where order matters but repeats are allowed (like counting the number of words you can make from a given set of letters).
These are not just a few more examples of the techniques we have developed in this chapter. Quite the opposite: everything we have learned in this chapter are examples of counting functions!
Example1.6.10
How many 5-letter words can you make using the eight letters \(a\) through \(h\text{?}\) How many contain no repeated letters?
SolutionBy now it should be no surprise that there are \(8^5\) words, and \(P(8,5)\) words without repeated letters. The new piece here is that we are actually counting functions. For the first problem, we are counting all functions from \(\{1,2,\ldots, 5\}\) to \(\{a,b,\ldots, h\}\text{.}\) The numbers in the domain represent the position of the letter in the word, the codomain represents the letter that could be assigned to that position. If we ask for no repeated letters, we are asking for injective functions.
If \(A\) and \(B\) are any sets with \(|A| = 5\) and \(|B| = 8\text{,}\) then the number of functions \(f: A \to B\) is \(8^5\) and the number of injections is \(P(8,5)\text{.}\) So if you can represent your counting problem as a function counting problem, most of the work is done.
Example1.6.11
How many subsets are there of \(\{1,2,\ldots, 9\}\text{?}\) How many 9-bit strings are there (of any weight)?
SolutionWe saw in Section 1.2 that the answer to both these questions is \(2^9\text{,}\) as we can say yes or no (or 0 or 1) to each of the 9 elements in the set (positions in the bit-string). But \(2^9\) also looks like the answer you get from counting functions. In fact, if you count all functions \(f: A \to B\) with \(|A| = 9\) and \(|B| = 2\text{,}\) this is exactly what you get.
This makes sense! Let \(A = \{1,2,\ldots, 9\}\) and \(B = \{y, n\}\text{.}\) We are assigning each element of the set either a yes or a no. Or in the language of bit-strings, we would take the 9 positions in the bit string as our domain and the set \(\{0,1\}\) as the codomain.
So far we have not used a function as a model for binomial coefficients (combinations). Think for a moment about the relationship between combinations and permutations, say specifically \({9 \choose 3}\) and \(P(9,3)\text{.}\) We do have a function model for \(P(9,3)\text{.}\) This is the number of injective functions from a set of size 3 (say \(\{1,2,3\}\) to a set of size 9 (say \(\{1,2,\ldots, 9\}\)) since there are 9 choices for where to send the first element of the domain, then only 8 choices for the second, and 7 choices for the third. For example, the function might look like this:
\begin{equation*}
f(1) = 5 \qquad f(2) = 8 \qquad f(3) = 4.
\end{equation*}
This is a different function from:
\begin{equation*}
f(1) = 4 \qquad f(2) = 5 \qquad f(3) = 8.
\end{equation*}
Now \(P(9,3)\) counts these as different outcomes correctly, but \({9\choose 3}\) will count these (among others) as just one outcome. In fact, in terms of functions \({9 \choose 3}\) just counts the number of different ranges possible of injective functions. This should not be a surprise since binomial coefficients counts subsets, and the range is a possible subset of the codomain.
While it is possible to interpret combinations as functions, perhaps the better advice is to instead use combinations (or stars and bars) when functions are not quite the right way to interpret the counting question.
SubsectionExercises
¶1
The dollar menu at your favorite tax-free fast food restaurant has 7 items. You have $10 to spend. How many different meals can you buy if you spend all your money and:
Purchase at least one of each item.
Possibly skip some items.
Don't get more than 2 of any particular item.
Solution
- \({9 \choose 6}\) meals.
- \({16 \choose 6}\) meals.
- \({16 \choose 6} - \left[{7 \choose 1}{13 \choose 6} - {7 \choose 2}{10 \choose 6} + {7 \choose 3}{7 \choose 6}\right]\) meals. Use PIE to subtract all the meals in which you get 3 or more of a particular item.
2
After a late night of math studying, you and your friends decide to go to your favorite tax-free fast food Mexican restaurant, Burrito Chime. You decide to order off of the dollar menu, which has 7 items. Your group has $16 to spend (and will spend all of it).
How many different orders are possible? Explain. (The order in which the order is placed does not matter - just which and how many of each item that is ordered.)
How many different orders are possible if you want to get at least one of each item? Explain.
How many different orders are possible if you don't get more than 4 of any one item? Explain.
3
After another gym class you are tasked with putting the 14 identical dodgeballs away into 5 bins. This time, no bin can hold more than 6 balls. How many ways can you clean up?
Solution\({18 \choose 4} - \left[ {5 \choose 1}{11 \choose 4} - {5 \choose 2}{4 \choose 4}\right]\text{.}\) Subtract all the distributions for which one or more bins contain 7 or more balls.
4
Consider the equation \(x_1 + x_2 + x_3 + x_4 = 15\text{.}\) How many solutions are there with \(2 \le x_i \le 5\) for all \(i \in \{1,2,3,4\}\text{?}\)
SolutionThe easiest way to solve this is to instead count the solutions to \(y_1 + y_2 + y_3 + y_4 = 7\) with \(0 \le y_i \le 3\text{.}\) By taking \(x_i = y_i+2\text{,}\) each solution to this new equation corresponds to exactly one solution to the original equation.
Now all the ways to distribute the 7 units to the four \(y_i\) variables can be found using stars and bars, specifically 7 stars and 3 bars, so \({10 \choose 3}\) ways. But this includes the ways that one or more \(y_i\) variables can be assigned more than 3 units. So subtract, using PIE. We get
\begin{equation*}
{10 \choose 3} - {4\choose 1} {6 \choose 3}.
\end{equation*}
The \({4 \choose 1}\) counts the number of ways to pick one variable to be over-assigned, the \({6 \choose 3}\) is the number of ways to assign the remaining 3 units to the 4 variables. Note that this is the final answer because it is not possible to have two variables both get 4 units.
5
Suppose you planned on giving 7 gold stars to some of the 13 star students in your class. Each student can receive at most one star. How many ways can you do this? Use PIE, and also an easier method, and compare your results.
6
Based on the previous question, give a combinatorial proof for the identity:
\begin{equation*}
{n \choose k} = {n+k-1 \choose k} - \sum_{j=1}^n (-1)^{j+1}{n \choose j}{n+k-(2j+1) \choose k}.
\end{equation*}
7
Illustrate how the counting of derangements works by writing all permutations of \(\{1,2,3,4\}\) and the crossing out those which are not derangements. Keep track of the permutations you cross out more than once, using PIE.
SolutionThe 9 derangements are: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
8
How many permutations of \(\{1,2,3,4,5\}\) leave exactly 1 element fixed?
SolutionFirst pick one of the five elements to be fixed. For each such choice, derange the remaining four, using the standard advanced PIE formula. We get \({5 \choose 1}\left( 4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4} 0!\right] \right)\) permutations.
9
Ten ladies of a certain age drop off their red hats at the hat check of a museum. As they are leaving, the hat check attendant gives the hats back randomly. In how many ways can exactly six of the ladies receive their own hat (and the other four not)? Explain.
10
The Grinch sneaks into a room with 6 Christmas presents to 6 different people. He proceeds to switch the name-labels on the presents. How many ways could he do this if:
No present is allowed to end up with its original label? Explain what each term in your answer represents.
Exactly 2 presents keep their original labels? Explain.
Exactly 5 presents keep their original labels? Explain.
11
Consider functions \(f: \{1,2,3,4\} \to \{a,b,c,d,e,f\}\text{.}\) How many functions have the property that \(f(1) \ne a\) or \(f(2) \ne b\text{,}\) or both?
SolutionThere are \(5 \cdot 6^3\) functions for which \(f(1) \ne a\) and another \(5 \cdot 6^3\) functions for which \(f(2) \ne b\text{.}\) There are \(5^2 \cdot 6^2\) functions for which both \(f(1) \ne a\) and \(f(2) \ne b\text{.}\) So the total number of functions for which \(f(1) \ne a\) or \(f(2) \ne b\) or both is
\begin{equation*}
5 \cdot 6^3 + 5 \cdot 6^3 - 5^2 \cdot 6^2 = 1260.
\end{equation*}
12
Consider sets \(A\) and \(B\) with \(|A| = 10\) and \(|B| = 5\text{.}\) How many functions \(f: A \to B\) are surjective?
Solution\(5^{10} - \left[{5 \choose 1}4^{10} - {5 \choose 2}3^{10} + {5 \choose 3}2^{10} - {5 \choose 4}1^{10}\right]\) functions. The \(5^{10}\) is all the functions from \(A\) to \(B\text{.}\) We subtract those that aren't surjective. Pick one of the five elements in \(B\) to not have in the range (in \({5 \choose 1}\) ways) and count all those functions (\(4^{10}\)). But this overcounts the functions where two elements from \(B\) are excluded from the range, so subtract those. And so on, using PIE.
13
Let \(A = \{1,2,3,4,5\}\text{.}\) How many injective functions \(f:A \to A\) have the property that for each \(x \in A\text{,}\) \(f(x) \ne x\text{?}\)
14
Let \(d_n\) be the number of derangements of \(n\) objects. For example, using the techniques of this section, we find
\begin{equation*}
d_3 = 3!-\left({3 \choose 1}2! - {3 \choose 2}1! + {3 \choose 3}0! \right)
\end{equation*}
We can use the formula for \({n \choose k}\) to write this all in terms of factorials. After simplifying, for \(d_3\) we would get
\begin{equation*}
d_3 = 3!\left(1 - \frac{1}{1} + \frac{1}{2} - \frac{1}{6} \right)
\end{equation*}
Generalize this to find a nicer formula for \(d_n\text{.}\) Bonus: For large \(n\text{,}\) approximately what fraction of all permutations are derangements? Use your knowledge of Taylor series from calculus.
