combinatorics - Combinations of words from letters: hard question.

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 :)

Answer

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.