- 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.
Answer is just 6*6*...*6=6^7
- 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.
- Choose 6 is just C(8+6-1,6)
- Choose 12: C(8+12-1,12) and Choose 24 is C(8+24-1,24).
- 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)
- 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.
- give 1 to x1 and then pick 20 from 5 with repetitions allowed.
- 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).
- 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).
- 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).