Revision as of 18:42, 3 February 2010

If anyone wants to work on this as a group, I'm willing. I'm struggling some and have class during his office hours. Call/text 317-605-6720. thanks.

Maybe we can get a group going every week...pick a night that we can meet and go over if we need help. If not then for sure before the midterm!

I think working in a group would be good. Weekly meetings definitely sound helpful...

HW3MA375S10

5.3 - 20, 22, 24, 32 | 5.4 - 21, 22, 28, 31, 38

I thought it would be nice to have a template for this week's homework so it would be easier to access information about the problems.

I like the template idea. This will be helpful!

Yea, awesome idea on the template. It is really convienient.

Great job! We need to do this every week!

Section 5.3

20. Does anyone know how to account for overcount in these problems? Or do you not have to take that into account

a) I'm struggling to get this one. It's not just 3 0's and pick the rest, it's exactly 3 0's. How would that effect the Permutation (or combination)?

Look at example 14 in section 5.3.

22.

• I am having problems with this one. I guess I just can't get the idea of it. Can anyone help?

Ok for this question, I think ED = DE so you take it as a block(or a single character), then you have 7 places to put all the characters. Same goes for the rest of the question, but the last 2 needs a little thinking.

The trick to these problems is basically to treat the strings they give you (ED, CDE, BA, FGH, etc.) as "blocks". In part A for example, you might imagine fusing letters E and D together. They are stuck to each other, so it makes sense conceptually to do that. Notice, however, that there are no longer eight "slots" in which you can insert your letters. There are actually seven, since in fusing E and D, you've fused two slots. The usefulness of this technique is not so evident in part A, but when you have to deal with multiple blocks (as in part C), it makes things much easier.

Look at part C, for instance. BA and FGH are two blocks. Because you've fused five different letters into two blocks, you've reduced the number of available "slots" by three. The advantage of this technique is that the problem now follows ordinary permutation rules. Your algorithm might be: pick the location of block BA (there are five ways to do this), pick the location of FGH (there are X ways to do this...) I'll leave the rest up to you.

24. I keep getting a small number for 24, but I know the answer should be larger. Can anyone help me?

Think about how we distinguished how many of each fruit we stole using dividers. Perhaps you need to take into account the permutations of the men and women.

 After looking at example 7, I decided to divide the men and women into 6 blocks of "WM" and then 4 "W"s. I'm not sure if this works, however. 

Think of it as this |*|*|*|*|*|*|*|*|*|*| the bars are men and star as women. You will have to choose 6 spots among the available ones. Then you also have to consider how you want to place the 10 women, but this is very simple, don't think too much for how to place 10 of them.

32. Any ideas on 32 b?

do we use the form (n!)/(n-r)!*r! on this portion or is it just n!/r! ?

The first form you mentioned is for combinations, and is used to reflect collections of unordered objects. The second form is for permutations, where the objects are ordered. In this case, the order of the letters definitely matters, and so you wish to distinguish between, say, "ABCDEF" and "FEDCBA". So this is a permutation type problem.

I thought this question is about "How many strings of six lowercase letters from the English alphabet contain..." ?

I don't think you are supposed to use the combinations/permutations formulas here. I interpreted a and b to mean that letters can be repeated, because c and d explicitly say that they can't be repeated

You might be right about repeatable letters. I really wish the text was more explicit. I'm going to have to do the problem again to account for both interpretations.

Did anybody talk to the professor about whether we can use letters multiple times in a and b?

Not that I know of. But these problems get much harder when you assume that letters can be repeated. I think they can be, because if they can't, the problems are pretty much the same as ones we did last week.

Section 5.4

21. Does anybody know how to show part a) without just using math to show that the two sides are equal (which we have to do for b). I'm stuck on how to go about this.

For the left side of the equation first consider the number of subsets you can make, then consider the number of elements you can pick out of any given subset then use product rule. For the right side of the equation, consider the number of elements you can choose, then remove it from the group to get n-1 element set and then consider the number of k-1 element subsets of that set. So you have a chosen element and a k-1 element subset that doesn't include your original pick, hope this helps.

22.

28. any idea for this problem?

Think of C(2n, 2) as picking 2 items from 2 sets of size n. Then look at the different ways possible to do this and combine those possibilities.

Anyone have an idea of how to explain the right side of the equation?

Here's how I thought of it. Look at the left side of the equation. It's telling you to choose two marbles from a sack of size 2n. That's simple enough. But suppose I take half the marbles out and put them in another sack. Then I have two sacks of size n. Now, if I tell you "pick two marbles (in total) from the sacks", has the situation changed at all? Nope, it hasn't. You're still drawing two marbles from a total pool of 2n marbles. But this visualization suggests an alternative way of thinking of the problem.

Let's call the first sack "A" and the second sack "B". You can break up all the possible marble choices into three categories, namely choices of the form:

(A, A) (B, B) and (A, B).

In other words, you can take BOTH of your marbles from sack A. Or you can take BOTH of them from sack B. OR, you can take one marble from each. Thinking of the problem in this way leads very directly to the right side of the equation.

Thanks! helped a lot!

31.

38.

Any ideas for this one?

Yea I'm stuck on this one too. I dont even think I know how to prove it algebraically.

Let's call our set of n elements "A". The left hand side says, pick a subset of A (that's the C(n,k) part), and then pick two not necessarily distinct elements, and mark them (that's the k^2) part.

In case it's not clear why that's the case, consider the terms C(n,0)+C(n,1)+C(n,2)+...+C(n,n). Such an expression counts all the subsets of A, because it counts all the subsets with 0 elements, then adds the number of subsets with 1 element, then adds the number of subsets with 2 elements, all the way until it reaches n.

The left hand side of the equation basically does this, but there's an extra k^2 attached. Where does the k^2 come from? Well, if, for every subset of A, you mark two not-necessarily-distinct elements, you get k^2. If you were forced to mark two DIFFERENT elements, then you'd have k choices for the first element, and (k-1) choices for the second. But this isn't k(k-1)... it's k^2. That means it's possible to mark the same element twice; you have k choices for BOTH marks. And this is where we begin to transform the left hand side into the right hand side.

We just saw that you can mark the same element twice. Okay. How about we PARTITION all of our choices into:

1) Choices where we mark the same element twice, and 2) Choices where we mark two different elements

Look at the expression the textbook gives at the end of the problem. It tells you to transform the right hand side of the equation into

$ n(n-1)2^{n-2}+n2^{n-1} $

These two terms actually correspond exactly to the partition we made. The first term reflects choices where you mark two different elements. The first "n" comes from the fact that there are n choices for the first mark. The (n-1) comes from there being one LESS choice for the second mark. What about the 2^(n-2)? Well, that part corresponds to creating all subsets of A. I don't want to give the whole thing away, but remember that membership in a set is a binary choice.

Back to 2010 Spring MA 375 Walther

Does anyone have any idea how the midterm is going to be,the pattern??

Yea, did he say what template he was going to use? Like a certain amount of problems or something?