HW7MA375S10 - Due Thursday, March 4th

6.4 - 6, 8, 12, 16 | 7.1 - 12, 24, 30, 36, 42, 44, 46

Section 6.4

6.

does the order of winning numbers set matter?

I don't think so. Typically, in a lottery, it's just a combination of numbers, not a permutation. For example, the combination "5, 10, 15, 20, 25, 30" would be the same as "30, 25, 20, 15, 10, 5."

So would it just be the 1 over the number of ways that we can make a 5 bit string out of 50 numbers?

8.

12.

I figured out the probability, but got a little confused about the expectation. Any hints? thanks

Hint: it's a geometric distribution. See pages 433-434 - specifically, Theorem 4 on page 434.

16.

Section 7.1

12.

Is there really ANY way to do this with counting principles? If we look at the total number of bit strings of length n with 3 consecutive zeros, for n = 3, 4, 5, and 6, we see 1, 3, 8, and 20. (It's 0 for any n < 3, of course.) Is there really a pattern there? Even if you look at the increments, it goes +1, +2, +5, +12; there is no discernible pattern, unless I'm just missing it. Any help?

Are you referring to problem 24 in section 7.1? Problem 12 does not refer to any bit strings. I take it you wish to solve the problem of finding a recurrence that describes the number of bit strings of length n which have three zeros in a row.

You are exactly right that there is no discernible pattern. That is exactly the point. In problems like these we ordinarily run a few experiments and try to figure out the pattern, but we can't do that here. You need to take an alternative route to figuring out the pattern, which is where recursion comes into play. It is generally easier to figure out how the present configuration of the system dictates the subsequent state, rather than coming up with a general rule that gives you the state of the system for any iteration.

For this problem you need to construct a tree. You wish to discover a_n. Consider investigating the first digit of the sequence. There are only two possibilities: either the bit is a zero or it is a one. If it is a one, then imagine snipping that digit off. You now have a sequence of length n-1, and you are asking yourself the same question: how many sequences of this length (n-1) have 3 consecutive zeros? This is a_(n-1). On the other hand, if the digit is a zero, then you must snip it off and move onto the next digit. Repeat and exhaust all the possibilities.

24.

30.

36. I'm totally lost, help please.

I broke down how many ways can 10 cents, 15 cents, and 20 cents be paid using tree diagram. Then, find the recurrence relation of a20 with respect to the others.

42.

Does anyone have any advice for this one?

When the top right domino is horizontal, you have a_(n-1) ways to permute. When it is vertical, you have a_(n-2) ways. This partitions all the possibilities so it should be clear what to do from there.

44. any idea about showing f5n is divisible by 5?

Use induction

46. i got 9 ways to parenthize x_0-x_4. is this correct because part B is confusing.

I don't think that's right. You can use the explicit formula in the example to find the correct number (part c).