Solutions 7 6.5: 10: For the purpose of this solution, bagels are croissants. (They have fewer letters to write.) a) Choosing 12 bagels from 6 types is like writing down 12 "b"'s and then separating them by 5 bars "|": the bagels to the left of the leftmost bar become plain ones, those between bars 1 and 2 become cherry, and so on. So this is the same as writing down 12+5 symbols, each either "b" or "|". To count the ways of doing this is the same as choosing 5 locations (for the bars) out of 17. So the answer is 17 choose 5. b) Same as above with 12 replaced by 36. c) Since we have to take 2 of each kind and there are 6 kinds, we really only get to choose bagels number 13, 14, ...,24. So the answer is the same as in a). d) There are 3 cases: no broccoli, one broccoli, or 2 broccoli. In the first case we are placing 4 separators between 24 bagels because we cannot take broccoli. So, 28 choose 4. If we take 1 broccoli, we are free to pick 23 more bagels, but we can't take broccoli any more. So, 27 choose 4. If we take 2 broccoli, 26 choose 4. The answer to d) is the sum of these 3 numbers. e) "At least 5 chocolate and at least 3 almond" implies that we can really choose only 24 - 5 - 3 = 16 bagels. So, (16+6-1) choose (6-1). f) We are forced to take 1+2+3+1+2 bagels of certain sorts. So we only choose 24 - 9 = 15. Then there are 4 cases: 0, 1, 2 or 3 broccoli. So, similar to d), (15+5-1) choose (5-1) plus (14+5-1) choose (5-1) plus (13+5-1) choose (5-1) + (12+5-1) choose (5-1). 18: 20!/(2!*4!*3!*1!*2!*3!*2!*3!). One can also write this as a product of 8 "chooses". 20: A solution to the given equation determines, and is determined, by a solution to x_1 + x_2 + x_3 + y =11, where y is a nonnegative natural number. In particular, to count the number of the former, we might as well count the number of the latter. But we know quite well that there are (11+4-1) choose (4-1) solutions to x_1+x_2+x_3+y=11, because we can imagine 11 ones being lined up and waiting for deportation to various buckets. Putting separators to indicate which bucket they go into, we need 4-1 of those... 24: Imagine you have 15 distinguishable food items and you have to eat them on one day: one for breakfast, two for lunch, three for afternoon tea, four for dinner, and five at midnight mass. How many ways are there to do this? Well, you could line them up in 15! different ways. But, at lunch you eat 2 things simultaneously, and that means there is no order between the two. Hence you over-counted by a factor of 2!. At tea, you over-counted by 3! because whether you eat the three items a, b and c as (abc) or (acb) or (bac) or (bca) or (cba) or (cab) made no difference since you ate them all at once. Similar for dinner and mass. So, 15!/(1!*2!*3!*4!*5!). 44: a) This is the question of putting 12 equal things into 4 labeled buckets. Which brings us back, mutatis mutandis (fancy Latin, used in various languages, meaning "changing that which needs to be changed"), to question 10 a). So, (12+4-1) choose (4-1). b) This is bit different. If the books were all the same, the answer would be 15 choose 3. However, for each way of putting certain numbers of books on the 4 shelves, there are 12! ways of rearranging the actual books WITHOUT changing the number of books one each shelf. So, (15 choose 3) * 12!. 46: This is similar to the one about men and women standing in line with no 2 men next to each other. Following the hint that is given we need to count the number of ways to arrange 5 bars and seven stars such that no two bars are adjacent. This boils down to asking in how many ways one can add three more stars to the following arrangement by either inserting them anywhere or placing them to the outside of the arrangement: |*|*|*|*| This amounts to counting in how many ways one can place 3 stars into 6 boxes. This number is (3+6-1 choose 6-1). 50: A nasty one. Let's say the "distinguishable objects" are the number 1,2,3,4,5. Suppose the buckets were labeled. Then putting the number 1,...,5 into 3 buckets would correspond to 3^5 possibilities, because for each number there are 3 choices. Now let's investigate what happens if we forget the labeling. For example, we could have 1,2 in box A, 3 in box B and 4,5 in box C. Somebody else might have had 1,2 in box C, 3 in box A and 4,5 in box B. We would now end up with the same UNLABELED distribution as the other fellow. How many labeled distributions do produce the same unlabeled distribution? Well, 3!, the number of ways of labeling 3 buckets with given content. Hence the number of unlabeled distributions is the number of labeled distributions divided by the number of labellings we have for each unlabeled distribution. So the answer is 3^5/6. Except that 6 does not divide 3^5. Ooops. What went wrong? Well, we were assuming that there are 3! ways of rearranging the labels on the boxes and creating each time a different labeled distribution. To ensure that is true, all buckets need to have DIFFERENT content. When does that fail? When 2 buckets are empty! (Note that one empty bucket is not a problem...) There are exactly 1 unlabeled ways of putting all numbers into one bucket. And there are exactly 3 labeled configurations that correspond to this: (all in bucket 1) or (all in bucket 2) or (all in bucket 3). This is the only way in which we might have gone wrong. It follows that of 3^5 labeled ways, 3 are giving rise to one unlabeled way, while the other 3^5 - 3 ways all arise as 6 versions of an unlabeled configuration. This means that the answer is (3^5 - 3)/6 + 1. Remarks: this remains true if 5 is replaced by some other number of you choice. It is instructive to explicitly write down the answer to the question "In how many ways can 3 labeled objects be put into 3 unlabeled boxes?", and to verify explicitly that there are (3^3-3)/6 +1 =5. Also, this formula needs modification beyond the obvious when 3 buckets become 4 or even more. You might try to figure it out for 4 along the above lines. Finally, you can also take a more pedestrian route by looking at cases: what if the bucket with the most numbers in them has 5 numbers in them? Then there is one way. If it has 4, there are are 5 ways (depending on which number is the lonely one). If the distribution is (3,2,0) then there are 5 choose 3 = 10 ways. If The distribution is (3,1,1) then there are also 5 choose 3 =10. If finally the distribution is (2,2,1) then there are 5 ways to pick the lonely guy and then 3 ways to decide on the two pairs. That gives 41 total. 54: Since we can't tell the objects or the bins apart, all thet matters is the numerical distribution of things. We could have object numbers (5,0,0), or (4,1,0), or (3,2,0), or (3,1,1), or (2,2,1). (Note that no order is given here, since we do not know which bucket is which.) 62: As many there are monomials of degree n in m variables. From class we know the answer: (n+m-1 choose m-1). 9.1: 8: a) Suppose a string of length n has 3 consecutive zeros in it. If the string S starts with 1 then the other n-1 bits must have 3 consecutive zeros. If the string starts with 01 then the other n-2 bits must have 3 consecutive zeros. If the string starts with 001 then the last n-3 bits must have 3 consecutive zeros. If S starts with 000 the other n-3 bits can be whatever they want. (And there are 2^(n-3) such strings.) Hence we have a recurrence a_n = a_(n-1) + a_(n-2) + a_(n-3) +2^(n-3). b) the initial conditions are a_0=a_1=a_2=0. (Note that the recursion is of order 3, so we need 3 conditions.) c) Since we are not asked to solve the recurrence, but just have to find a_7, we can do it step by step: a_3=a_0+a_1+a_2+2^0 = 1. a_4=a_1+a_2+a_3+2^1 = 1+2=3. a_5=a_2+a_3+a_4+2^2 = 1+3+4 = 8. a_6=a_3+a_4+a_5+2^3 = 1+3+8+8 = 20. a_7=a_4+a_5+a_6+2^4 = 3+8+20+16 = 47. 14: a) All ternary strings either start with 00, or with 1, or with 2, or with 01, or with 02. If S starts with 00, the other n-2 digits can be what they want, so there are 3^(n-2) such strings. In all other 4 cases, if the original string had 2 consecutive zeros, then dropping the 1, or 2, or 01, or 02 at the start will have no effect. So the recurrence is 1* 2* 01* 02* 00* a_n = a_(n-1) + a_(n-1) + a_(n-2) + a_(n-2) +3^(n-2). b) The recurrence has order 2, so we need 2 initial conditions. They are a_0=a_1=0. c) a_2=2*a_1+2*a_0+3^0=1. a_3=2*a_2+2*a_1+3^1=5. a_4=2*a_3+2*a_2+3^2=21. a_5=2*a_4+2*a_3+3^3=79. a_6=2*a_5+2*a_4+3^4=281. 20: a) Let a_n be the number of ways to pay 5*n cents, clearly one cannot pay tolls that are not divisible by 5. The first coin of any payment may be a nickel or a dime. If it's a nickel, he needs to pay a further n-5 cents, which can be done in a_(n-1) ways. If the first is a dime, the other n-10 cents can be paid in a_(n-2) ways. So a_n=a_(n-1)+a_(n-2). b) We note that the initial conditions are a_1=1 and a_2=2 (10 or 5+5). Hence a_1=1, a_2=2, a_3=3, a_4=5, a_5=8, a_6=13, a_7=21, a_8=34 and a_9=55. 26: a) Let a_n be the number of ways one can tile the 2xn board with tiles as indicated. If the top right corner is an upright 1x2 piece, the left 2x(n-1) board can be covered in a_(n-1) ways. If the top right corner is a flat 2x1 piece, underneath it must be another one. Then the other 2x(n-2) board can be covered in a_(n-2) ways. So a_n=a_(n-1)+a_(n-2). b) A 2x1 board can be covered in 1 way, a 2x2 board in 2 (2 horiontal tiles, or 2 vertical tiles). So a_1=1, a_2=2. c) We have the same recurion and initial conditions as in the previous question, so a_10=89, a_11=144, a_12=233, a_13=377, a_14=610, a_15=987, a_16=1597, a_17=2584. 28: The Fibonacci recurrence is f_n=f_(n-1)+f_(n-2). If you plug this into itself you get f_n=f_(n-1)+f_(n-2) =(f_(n-2)+f_(n-3))+f_(n-2) = 2*f_(n-2)+f_(n-3) =2*(f_(n-3)+f_(n-4))+f_(n-3) = 3*f_(n-3)+2*f_(n-4) =3*(f_(n-4)+f_(n-5))+2*f_(n-4) = 5*f_(n-4)+3*f_(n-5). Obviously, the first 5 Fibonacci's are the ones given in the book, and since we have now a recurrence of depth 5 we need just these five initial conditions to specify the sequence. Since f_5=5, it clearly is divisible by 5. Since by what we found above, f_(5k)=5*f_(5k-4) + f_(5k-5), the questions "is f_(5k) divisible by 5?" and "is f_(5k-5) divisible by 5?" are equivalent, since the difference of the two numbers is a multiple of 5. But 5 divides f_0, so also 5 divides f_5, so also 5 divides f_10,... 30: a) I'll just write stars for the variables. (((**)*)*)* ((*(**))*)* ((**)(**))* (*((**)*))* (*(*(**)))* (*(**))(**) ((**)*)(**) (**)(*(**)) (**)((**)*) *(((**)*)*) *((*(**))*) *((**)(**)) *(*((**)*)) *(*(*(**))) Note, how the first 4 are the ones from Example 8 with a final multiplication at the end, the last 5 are the 5 from the book with a final multiplication at the end, and the middle 2+2 are the middle terms of the recurrence, corresponding to parenthesizing 3 and 2 or 2 and 3 variables respectively and finally multiplying the two blocks. b) C_4=C_0*C_3+C_1*C_2+C_2*C_1+C_3*C_0 = 1*5 + 1*2 + 2*1 + 5*1 = 14. c) C(2n,n) is 2n choose n. If n=4, C(2n,n)=8 choose 4 = 8*7*6*5/1*2*3*4 = 70. Dividing this by n+1=5 we get 14. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%