In how many ways can a person choose one or more out of 5 different subject books
Suppose you have a huge box of animal crackers containing plenty of each of 10 different animals. For the counting questions below, carefully examine their similarities and differences, and then give an answer. The answers are all one of the following: Show \(P(10,6)\qquad\)\({10 \choose 6}\qquad\)\(10^6\qquad\)\({15 \choose 9}.\)
You have 9 presents to give to your 4 kids. How many ways can this be done if:
Solution For each of the following counting problems, say whether the answer is \({10\choose 4}\text{,}\) \(P(10,4)\text{,}\) or neither. If you answer is “neither,” say what the answer should be instead.
Solution Neither. \({14 \choose 4}\) paths. Neither. Assuming you will wear each of the 4 ties on just 4 of the 7 days, without repeats: \({10\choose 4}P(7,4)\text{.}\) Neither. Since you could repeat letters: \(10^4\text{.}\) If no repeats are allowed, it would be \(P(10,4)\text{.}\) Neither. Actually, “k” is the 11th letter of the alphabet, so the answer is 0. If “k” was among the first 10 letters, there would only be 1 way - write it down. Neither. Either \({9\choose 3}\) (if every kid gets an apple) or \({13 \choose 3}\) (if appleless kids are allowed). Neither. Note that this could not be \({10 \choose 4}\) since the 10 things and 4 things are from different groups. \(4^{10}\text{.}\) Neither. \(16^{10}\) (each kid chooses yes or no to 4 varieties). Neither. 0. Neither. \(4^{10} - [{4\choose 1}3^{10} - {4\choose 2}2^{10} + {4 \choose 3}1^{10}]\text{.}\) Neither. \(10\cdot 4\text{.}\) Neither. \(4^{10}\text{.}\) Neither. If all the kids were identical, and you wanted no empty teams, it would be \({10 \choose 4}\text{.}\) Instead, this will be the same as the number of surjective functions from a set of size 11 to a set of size 5. Neither. \(4!\text{.}\) Neither. It's \({10 \choose 4}\) if you won't repeat any choices. If repetition is allowed, then this becomes \(x_1 + x_2 + \cdots +x_{10} = 4\text{,}\) which has \({13 \choose 9}\) solutions in non-negative integers. Neither. Since repetition of cookie type is allowed, the answer is \(10^4\text{.}\) Without repetition, you would have \(P(10,4)\text{.}\) Neither. It will be a complicated (possibly PIE) counting problem. Recall, you own 3 regular ties and 5 bow ties. You realize that it would be okay to wear more than two ties to your clown college interview.
Solution You have 7 choices for regular ties (the 8 choices less the “no regular tie” option) and 31 choices for bow ties (32 total minus the “no bow tie” option). Thus total you have \(7 \cdot 31 = 217\) choices. Select one of the 3 bow ties to go on top. There are then 4 choices for the next tie, 3 for the tie after that, and so on. Thus \(3\cdot 4! = 72\) choices. To thank your math professor for doing such an amazing job all semester, you decide to bake Oscar cookies. You know how to make 10 different types of cookies.
Solution For which of the parts of the previous problem (Exercise 1.7.19) does it make sense to interpret the counting question as counting some number of functions? Say what the domain and codomain should be, and whether you are counting all functions, injections, surjections, or something else. Solution You are giving your professor 4 types of cookies coming from 10 different types of cookies. This does not lend itself well to a function interpretation. We could say that the domain contains the 4 types you will give your professor and the codomain contains the 10 you can choose from, but then counting injections would be too much (it doesn't matter if you pick type 3 first and type 2 second, or the other way around, just that you pick those two types). We want to consider injective functions from the set \(\{\)most, second most, second least, least\(\}\) to the set of 10 cookie types. We want injections because we cannot pick the same type of cookie to give most and least of (for example). This is not a good problem to interpret as a function. The problem is that the domain would have to be the 12 cookies you bake, but these elements are indistinguishable (there is not a first cookie, second cookie, etc.). The domain should be the 12 shapes, the codomain the 10 types of cookies. Since we can use the same type for different shapes, we are interested in counting all functions here. Here we insist that each type of cookie be given at least once, so now we are asking for the number of surjections of those functions counted in the previous part. |