6
$\begingroup$

How many ways can the letters of the word TOMORROW be arranged if the Os cant be together?

I know TOMORROW can be arranged in $\frac{8!}{3!2!} = 3360$ ways. But how many ways can it be arranged if the Os can't be together? And what is the intuition behind this process?

2 Answers 2

11

We interpret the question as saying we cannot have two (or three) O's together. Think of the slots occupied for the remaining $5$ letters. There are $6$ spaces "between" these slots for the O's to be squeezed into, no more than one O per space. Here the number of spaces is $6$ because I am counting the two endspaces.

We choose $3$ of these $6$ spaces for the O's. This can be done in $\dbinom{6}{3}$ ways.

For each of these ways, the T can be placed in $5$ ways, then the M in $4$ ways, then the W in $3$ ways. Now it is all done, the R's take the remaining two slots. So our count is $$\binom{6}{3}(5)(4)(3).$$

Remark: There are many other ways of counting. The advantage of this one is that it generalizes smoothly to a situation where the length of the word, and the number of O's, is much larger.

The idea can be adapted for similar problems. A standard one is to ask how many ways can we line up $9$ adults and $5$ children in a row if no two childen can be next to each other.

  • 4
    I'm so frustrated by combinatorics. I SWEAR,I WILL SLAY THIS DRAGON BEFORE I LEAVE THIS LIFE!!!2012-11-21
  • 0
    @Andre: could you please explain again why there are 6 spaces for O and how this accounts for the fact that 2 or 3 O's can't be together?2013-06-17
  • 2
    Imagine that the other $5$ letters occupy slots X X X X X. The O's need to be separated, so any O can be placed into a space between two X's, or into one of the two ends, just before the first X or just after the last. There are $4$ inter-X spaces, and $2$ endspaces, for a total of $6$. We must choose $3$ of these $6$ spaces to put O's into.2013-06-17
  • 0
    OF course, thanks!2013-06-17
1

First, you have to remove the permutations like this TOMOORRW and TMOOORRW, so see OO as an element, then we have $3360-\frac{7!}{2!}$.

EDITED

Now, Notice you remove words like this TOMOORRW and TMOOORRW with OO and OOO, but you remove a little bit more you want, why? can you see this? how to fix this problem?