Solutions 6 Section 6.3 20: a) To have 3 zeros means to have 7 ones. To count you just have to decide where the 0's go, for which there are 10 choose 3 ways. b) There are 6 or 7 or 8 or 9 or 10 0's. So there are (10 choose 6) + (10 choose 7) + (10 choose 8) + (10 choose 9) + (10 choose 10) such strings. c) There are 7 or 8 or 9 or 10 1's, so there are (10 choose 7) + (10 choose 8) + (10 choose 9) + (10 choose 10) such strings. d) (10 choose 3) + (10 choose 4) + ... + (10 choose 10). Alternatively: 2^(10) - (10 choose 0) - (10 choose 1) - (10 choose 2). (Why?) 22: a) It's like having 7 letters a,b,c,de,f,g,h. So 7! permutations. b) It's like having letters a,b,cde,f,g,h. So 6! permutations. c) Letters ba,c,d,e,fgh. So 5!. d) Letters ab,c,de,f,gh. So 5!. e) The string "cab" must be followed by the string "ed" as otherwise "bed" cannot be part of the word. So there are letters cabed,f,g,h. So 4!. f) This can't happen. 24: First place the women in line. Now between any 2 adjacent women only one or zero men can be inserted. Hence the job at hand is equivalent to choosing where in the 11 possible places next to women (why are there 11 if there are only 10 women?) the 6 men are inserted. This gives 11 choose 6. However, the order of the men is important since they are different people. Once you have decided WHERE the guys stand (for example in positions 2,4,6,8,11 and 15), we now have to count in how many ways we can place them into just that pattern. This gives 6!. Similarly for the women there are 10! ways of deciding which is the first one, which the second and so on. So altogether we get 6!*10!*(11 choose 6). 32: a) There are 26^6 words of length 6. Of these, 25^6 have no "a". So 26^6 - 25^6 have an a. b) 24^6 have neither a nor b. Inclusion/exclusion dictates that there are 26^6 - 25^6 - 25^6 + 24^6 with both a and b. c) We are counting words with 5 distinct letters chosen from the alphabet ab,c,d,...,z of 25 letters (ab is one single letter), but we insist that "ab" occurs. There are 5 ways of choosing where the "ab" goes. Then 24 letters are left to fill the 4 other positions. This gives 5*24*23*22*21. d) There are 6 choose 2 ways of positioning the a and the b (since we know that a comes before b). Then there are 24 letters left to fill the remaining 4 spots, which can be done in 24*23*22*21 ways. So the answer is 15*24*23*22*21. Section 6.4: 21: a) Using algebra, plug in the formula for n choose k and simplify. In both cases you end up with n!/( k-1)!*(n-k)! ). b) This is more interesting. Imagine the job at hand: n fishes are in a pool, you come with a fish-net and catch k of them, and once you are home fry one of them. Let's count in how many ways that can be done. Fishing out k from n is possible in n choose k ways. Then at home you have k choose one way of picking the one you will fry. So there are (n choose k) times (k choose 1) ways of doing the job. Note that k choose 1 equals k, so the number of ways the job can be done equals the left hand side of the equation we have to prove. Now picture yourself doing this over again. You are trying to catch k fish from n, but somehow only one fish ended up in the net. You decide you are too hungry and fry it right there one beach. After lunch, you get back to the job and catch the other k-1 (note the "minus 1" !!!) fish to make sure you caught k altogether. In how many ways can this be done? Well, n choose 1 for the one eaten on the beach. And n-1 choose k-1 for making sure k have been caught. That makes n times n-1 choose k-1. In both paragraphs one fish was fried and eaten and k-1 are in the net and n-k are still in the pond. So the numbers we came up with for counting the two procedures are the same, finishing the proof. 22: It's the same as in 21, only that this time there are n fish in the pond, we fish out r with the net, and at home eat k of them. Thinking of the process in this order gives you n choose r for the fishing part, and then r choose k for the selection of lunch. Thinking of it the other way round you get n choose k for having lunch on the beach, and then n-k choose r-k to complete the job. 28: Let us count the number of ways in which one can choose 2 things from 2n. Obviously there are 2n choose 2 such. Imagine now that n of the things are blue and n are red. They may not be in reality, but that does not stop us from imagining! There are 3 kinds of pairs we might end up with, 2 red, 2 blue, or one of each. To get 2 red there are n choose 2 ways, same for getting 2 blue. To get one each there are n ways to choose the red, and n ways to choose the blue. This means that summing up all possibilities we have (n choose 2) plus (n choose 2) plus n*n ways. 31: Let's say our big set has n elements. If we pick a subset with an even number, it has either 0, or 2, or 4, or... elements. To pick one with 0 elements there are n choose 0 ways. To get one with 2 there are n choose 2 ways, and so on. So we want to show that the sum (n choose 0) + (n choose 2) + (n choose 4) + ... equals the sum (n choose 1) + (n choose 3) + (n choose 5) + ... for all n. To do this, recall the binomial theorem we saw in class: n (x+y)^n = sum (n choose i) x^i y^(n-i) i=0 and recall also that we played around with plugging numbers into this identity. For example, x=-1 and y=1 produce 0 on the left and on the right (n choose 0) - (n choose 1) + (n choose 2) - (n choose 3) + ... -... which proves what we want. 38: The given job is: a pond has n fishes. Catch some, and then fry one of those caught and then sell one of those caught. Note: we may sell the one fried, or we may sell one of the raw ones. How many ways are there to do this? Version 1: First decide how many we catch, say k. To catch k fish from n allows for n choose k possibilities. Then there are k ways to fry one, and k ways to sell one. So for each k, we get a contribution equal to (n choose k)*k*k. Summing this over all k between 0 and n we obtain the left hand side of the equation we are to show. Version 2: First catch one and fry it: n choices. Next decide which one to sell: also n choices. But the requirement is that you need to catch it first. There are 2 cases: if we sell the fried one, no worry. In that case we just need to catch some more fish (allowing for 0 more) and be done. Since the pond has now n-1 fish, there are 2^(n-1) ways of completing the job. (Recall that the number of subsets of a given set is 2 to the number of elements in the set.) So this case contributes n*2^(n-1). The other case is when we want to sell one we have not caught yet. Catching and selling it allows for n-1 possibilities. To complete the job, we need to catch some more and be done. Since now just n-2 fish are in the pond there are 2^(n-2) ways of catching more fish. This gives a total of n*(n-1)*2^(n-2) arising from case 2. Adding cases 1 and 2 we get a total of n*2^(n-1) + n*(n-1)*2^(n-2) = 2*n*2^(n-2) + n*(n-1)*2^(n-2) = n*(n+1)*2^(n+1).