## Assigned Problems 4.6

• 4-6 P290: 3, 4, 9, 11, 15, 21, 22, 25, 27, 35, 37, 40

• Problem 4 Six kinds of sandwiches in a pile, 7 ordered choices.

• Problem 9 Eight kinds of bagels: Choose 6; Choose 12; Choose 24; Choose 12 with at least one of every kind; Chose 12 with at least 3 of one particular one and no more than 2 of another particular kind.

1. Choose 6 is just C(8+6-1,6)
2. Choose 12: C(8+12-1,12) and Choose 24 is C(8+24-1,24).
3. Choose 12 with at least one of every kind. Just first pick in exactly one way, one of every kind. Now you are just picking 4 from 8 with repetitions: C(8+4-1,4)
4. We can handle the"at least 3" by just first picking 3; hence we are really looking at Pick 9 from 8. But to handle the"no more than 2" we could split into 3 cases: pick exactly 0, 1, 2 of that particular kind and add the results. Another way is as follows: Pick how many with no restrictions and take away all those that violate the restriction: C(8+9-1,9) - C(8+6-1,6) because this second number C(8+6-1,6) represents how many ways to pick 9 from 8 with at least 3 of the bad kind.

• Problem 11 8 coins from 100 identical pennies and 80 identical nickels.

It doesn't matter how many pennies as long as there are at least 8. Choose 8 from 2 with repetitions allowed.

• Problem 15 How many solutions SUM(xi : i=1...5}=21 from non-negative integers such that: x1>=1; each xi at least 2; x1 no more than 10; x1 at most 3, 1<x2<4 and x3>=15.

1. give 1 to x1 and then pick 20 from 5 with repetitions allowed.
2. each xi at least 2. Give 2 to each xi, leaving the need to pick 11 more. So now choose 11 from 5: C(11+5-1,11).
3. x1 no more than 10: All possible (C(21+5-1,21)) minus those that have x1 >10, which is C(11+5-1,11).
4. x1 at most 3, 1<x2<4 and x3>=15 Give 1 to x2, and 15 to x3 leaves us with a new problem to pick 5 from 5. This latter comes with the restriction that x1 is at most 3 and x2 is at most 3. Without restriction we just have C(5+5-1,5). Subtract from this the number of solutions in which x1> 3 and/or x2>3. Luckily there is no overlap, they cannot both be bigger than 3, therefore it is just: give 4 to x1 and choose 1 from 5 plus give 4 to x2 and choose 1 from 5.

• Problem 25 Bit strings starting with 1, having 3 more 1's, 12 0's and every 1 is followed immediately by 2 0's.

Put a 1 at the beggining and immediately put 2 0's after it. This leaves us with 3 1's and 10 0's to place. For each of the 1's take 2 0's and make an unbreakable group"100". This gives us 3 identical groups of"100" and 4 singleton 0's. Arrange these 7 objects in all distinguishable ways. C(7,3) = C(7,4) i.e. lay out the seven objects in 7 positions and choose 3 positions to place the"100"'s (or equivalently choose 4 places to put the 0's).

• Problem 27 ABRACADABRA using all letters.

11 letters, 5 A's and 2 B's, 2 R's, 1 C, 1 D. Answer 11!/(5!*2!*2!)

• Problem 35 3-D space from (0,0,0) to (4,3,5) only in positive unit steps. We must move x direction 4 times, y direction 3 times, z direction 5 times. Just lay out 4 x's, 3 y's and 5 z's in all possible ways. This is 12 objects, 4,3, and 5 rep's. So 12!/(4!*3!*5!). By the way, your calculator may be incapable of handling 12!. Don't make it. Cancel first. 12!/5! = 12 11 10 9 8 7 6; 3! is 6, 4! = 12 * 2. Cancel stuff to get e.g.: 11 5 10 9 8 7.

• Problem 37 7 cards to 5 players from deck of 52.

Routine: 52! / (7!*7!*7!*7!*(52-4*7)! OR
C(52,7)*C(52-7,7)*C(52-14,7)*C(52-21,7).

• Problem 40 12 books on 4 distinct shelves. Part a: all books the same, part b: 12 distinct books.

The tricky part here is that we don't know how many books go on each shelf. In part (a) that's all we have to determine. xi is the number of books that go on the i-th shelf. So we have x1+x2+x3+x4=12 and find all solutions.
Part (b) is much harder. Let the books be numbered 1 to 12. Take book 1 and decide where to put it (4 choices). Now take book 2 and decide how many ultimately distinct ways there are to put it (relative to book 1). There are 5 choices: one of the three other shelves, or if on the same shelf, which side of book 1. Worded for generalization: pick a shelf and put it to the left of everything else on the shelf or pick a book already placed and put it immediately to the right of that book. Now book 3: 4 choices for farthest left on a shelf and two choices for immediately to the right of a placed book. In general, placing book i you have 4 extreme left positions plus (i-1) positions to be to the right of an old book. Multiply all this together for:
4*5*6*7*8*...*(4+11).