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?

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ I'm so frustrated by combinatorics. I SWEAR,I WILL SLAY THIS DRAGON BEFORE I LEAVE THIS LIFE!!! $\endgroup$ – Mathemagician1234 Nov 21 '12 at 8:43
  • $\begingroup$ @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? $\endgroup$ – Alex Jun 17 '13 at 17:12
  • 2
    $\begingroup$ 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. $\endgroup$ – André Nicolas Jun 17 '13 at 17:31
  • $\begingroup$ OF course, thanks! $\endgroup$ – Alex Jun 17 '13 at 17:41
1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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