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...

Would someone like to perhaps make a facebook group for a MA 375 study group? We could have physical meetings and have discussions of homework problems right there on the group's wall. (Then again, I guess that's what Rhea's for... but the facebook group would at least help us organize meetings, send messages to members, etc.)

Would wednesday evenings work for anyone? This would be a good time to finish the assignment if we are stuck on any problems.

# 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!

I like to do it!

## 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.

Also, keep in mind that the men may be placed in different arrangements. If you use the combinatorial ("choose") function, nCr, keep in mind that it doesn't care about the order of the members of its r-groups, only what members make it up--different orders are not counted separately. So, you need to take into account how to permute the members.

You can arrive at the answer by multiplying the number of ways to arrange the 6 men * the number of ways to arrange the 10 women * the number of ways to create a line arrangement. The first two are easy factorials. The last requires some thought though. Since we need to have a woman between each man, you know that it has to go M W M W M W M W M W M. The remaining 5 women can be placed anywhere in the line, hope this helps.

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.

I ended up getting a bigger answer for part c than for part a or b, but that seems impossible...

For part a, I used the logic that the total number of ALL 6-letter strings is 26^6, and the total number of 6-letter strings that DON'T have an "a" is 25^6, so the total number of 6-letter strings with AT LEAST ONE "a" is 26^6 - 25^6 = 64,775,151. Does that seem right?

Then for part b, I used similar logic: I took the total number of 6-letter strings, subtracted the number of 6-letter strings that don't contain "a," subtracted the number that don't contain "b," and added back in the number that contain both "a" and "b" to account for the fact that those were subtracted out twice; my answer to "b" was then 26^6 - 2*25^6 + 24^6 = 11,737,502.

For part c, I counted the number of 6-permutations of 25 objects - namely, the block "ab" and the letters c-z. That gave me P(25, 6) = 127,512,000.

The thing is, it seems like part c should be smaller than a or b, since strings containing "ab" are a subset of strings containing "a." What have I done wrong?

(It's also worth noting that part d has me stumped... I have no idea how one would go about counting the cases in which one letter appears to the left of the other...)

## 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.

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?

Will he go over some practice questions from the suggested ones online or does he have like a practice test we can prepare with?---RPK

TQU: there are practice problems online and even on RHEA, look under the old RHEA. Anybody interested to form a study group before the midterm?

## Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.