Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have this question as follows...

Take the word BEBBEDREB

Out of all distinct words that can be made using all letters of the word - how many have no letter in the same place as the original word?

So far I've worked out how many distinct words there are like so... There are 9 letters so 9! ways of arranging them, however, there are 3 repeated E's and 4 repeated B's which have 3! and 4! arrangements that occur in the 9! combinations which makes them non distinct. Eg, 'BEB' and 'BEB' shouldnt be counted twice.

So 9!/(3!*4!) = 2520 distinct words.

But now the problem is, I dont know how many of these words have no letter in the same place as the original word and I dont know how to go about it exactly.

Any help would be greatly appreciated. Thank you :)

share|improve this question
1  
I just answered a very similar question; see if you can adapt the reasoning there to this problem. –  Brian M. Scott Oct 6 '13 at 9:42
    
@BrianM.Scott Thank you so much for that answer. My brain officially hurts now but I learnt a lot. –  Ogen Oct 6 '13 at 10:50
    
:-) You’re welcome. –  Brian M. Scott Oct 6 '13 at 17:36
    
@BrianM.Scott: I didn't realize the similarity extended to a letter substitution... –  hardmath Oct 7 '13 at 12:46
    
@hardmath: Damn, it does, doesn’t it? I didn’t notice at the time. –  Brian M. Scott Oct 7 '13 at 19:06

1 Answer 1

up vote 2 down vote accepted

When it is necessary to count by dividing possibilities into "cases", you generally want to identify the aspect of the solutions that is most constraining.

Here we have four $B$'s and five positions into which those $B$'s can be placed. That can be done in 5 ways, so it's a good starting point if we have to "divide into cases":

Original word:   BEBBEDREB
Possible case:   -B--BBB?-
Possible case:   -B--BB?B-
Possible case:   -B--B?BB-
Possible case:   -B--?BBB-
Possible case:   -?--BBBB-

We then have to pursue each case further, but it may be that some cases are alike and simplify our counting on that basis. Here we have assigned locations to the $B$'s in each of the 5 cases, and what remains is to assign the non-$B$ characters, three $E$'s and one $D$ and one $R$.

What goes in the ? position indicated above depends on what was there in the original word, as the new symbol must differ from the original one. In the 3 cases where the original symbol was $E$, the two choices are $D$ and $R$ for the new word in that position. Further, once that choice is made, all the remaining arrangements are legitimate, in that the last four positions were originally $B$'s and will now be assigned non-$B$ symbols.

So for these 3 cases, we choose 2 possible symbols ($D$ or $R$) for the question mark position, and then we have any possible arrangement of the three $E$'s and one non-$E$ symbol (whichever $D$ or $R$ is left from that last choice). Now the three $E$'s go into the four locations in 4 ways (basically just choose the location of the non-$E$).

Altogether these cases have 3*2*4 solutions.

That leaves the other two cases of the 5 outlined above, where the ? occurs under the $D$ or under the $R$. Again we have two choices for the symbol to be placed there, either an $E$ or the "opposite symbol" ($D$ in place of $R$ or vice versa). Any arrangement of the remaining four symbols is again legitimate (since they will go in slots previously occupied by $B$'s), but there is a slight twist.

If we choose $E$ to go in the ? slot, we are left with two $E$'s, one $D$ and one $R$, and there would be 12 ways to arrange those four symbols (think about picking a location for $D$ and then one for $R$). But if we choose $D$ or $R$ as "opposite" to go in the ? slot, we are left with three $E$'s and one non-$E$ symbol, and so as before 4 ways to arrange them.

Altogether for these last 2 cases we thus have 2*(12+4) solutions. Combining the results for all 5 cases, there are 3*2*4 + 2*(12+4) = 56 solutions.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.