Three Problems from Discrete

Here are three problems from the review sheet for Discrete Math. They are all counting problems. I'll post other types, too, but these ones are the trickiest, personally.

1. Question: In how many ways can 12 (identical) apples be distributed among 5 (distinct) children so that no child gets more than 7 apples?
   Solution: This is a "bins" problem. Let's look at the total number of ways of distributing the apples, without the qualifier. There are 12 apples and 5 children; thinking of the children as apple-receptacles (bins), there are 4 dividers between the 5 bins. So, there are 12+4=16 total objects -- 12 items and 4 dividers -- so I need to decide where to put 12 apples OR 4 dividers in a total of 16 objects. Then, the total number of ways to distribute the apples is 16C12=16C4. However, this includes the possibility that one kid will have at least 7 apples. Let's now assume that one kid does indeed at least 7 apples; giving him or her 7 apples off the bat reduces our number of objects from 16 to 9. So, there are 9C5=9C4 ways of distributing the remaining 5 apples. However, there are 5 different kids, so each of these combinations can occur 5 different times. So, there are really 5(9C5) ways of distributing the remaining 5 apples. Of course, we want the situation in which this DOESN'T happen, so the real solution is the total distributions minus the unwanted distributions, or 16C4-d(9C4).
   
2. Question: How many arrangements of all of the letters of JUPITER are there with the vowels occurring in alphabetical order (but not necessarily consecutively)?
   Solution: Let's focus just on the vowels first. There are three vowels, and they need to be in the order EIU. There are seven spaces total, so there are 7C3 ways to distribute the vowels; of course, if there were no alphabetical qualifier, then there would be 3(7C3) ways to distribute the vowels, but, since they MUST go in a certain order, there is really 1(7C3) ways. Now, we have 4 remaining letters, each of which must be used once. So, there are 4! ways to distribute them. Then, there are 4!(7C3) possible arrangements.
   
3. Question: At a birthday party, 36 identical balloons are distributed to 8 distinct children. If the balloons are distributed randomly, what is the probability that one child will get 20 or more balloons?
   Solution: This is a probability question, so I'm going to do it in 2 (or 3) steps. First, I'm going to figure out what the denominator will be. In this case, it will be the total ways of distributing the 36 balloons. Again, this is a bins problem, and there are 36 items and 8 bins (with 7 dividers), so there are 43 objects. Then, the total number of distributions is 43C7. This is the denominator. However, we want the ways in which the one kid gets 20 or more balloons. This will be the numerator. Let's give one kid 20 balloons, just give 'em away. Then, there are 23 objects left (36-20+8-1=23). So, there are 23C7 distributions; again, however, there are 8 kids, so the numerator is 8(23C7). Then, the probability is 8(23C7)/(43C7).
   

These are just my answers. I'll edit in corrections when the answers are posted. Tomorrow (or maybe later today), expect some problems concerning recurrence relations, functions, and equivalence relations. For now, I'm off to study PHL.