A bus has to visit three cities, each of them four times. The number of ways it call be done if bus is not allowed to start. and end in the same city is?
(A) 1260 (B) 1120 (C) 980 (D) None of the above.
My approach
Suppose we name the cities as A,B and C.
Then the problem is to find the number of arrangements such that no two same letters occur together. But I can't find that too.
Thus we have ABCABCABCABC is one way. But AAAABBBBCCCC is not a proper one.
But I can't find the number of such permutations where no same letter occur together.
Please help or give a different hint to tackle the problem.
Let consider the sequences of letters $AAAABBBBCCCC$ which start with $A$. We consider the four blocks $AX$ where $X$ can be either $B$ or $C$. The first block is placed as the first one so we have to arrange three remaining blocks over 7 available positions. There are altogether $\binom 73=35$ ways to do this. We can classify the sequences by the structure of the gaps between the $AX$ blocks as shown in the following table: $$\begin{array}{c|r|c|r} \text{Gap} (1234)& N& NN&N\times NN\\ \hline (4000)&1&2^4&16\\ (2100)&12&2^3&96\\ (1010)&12&2^2\binom21&96\\ (0200)&6&2+2^2&36\\ (0001)&4&2\binom31&24\\ \hline &35&&268 \end{array}$$
The gap structure (first column) is labeled by the number of gaps with sizes $1,2,3,4$. Second column shows the number of sequences with the given gap structure and the third column shows the number of ways to fill the given gaps (together with $X$'s from the blocks).
For example the sequences with two gaps of size 2 can be filled as follows. Consider the blocks $AX$ adjacent to the gaps (from the left). The two corresponding $X$ can be filled either with the same letter or with different ones. In the first case we are left with two identical letters to fill $X$ in the remaining two blocks, so there is no actual choice. In the second case two different letters remain. Hence there are in total $2+2^2=6$ ways to arrange the letters. Similarly one can consider the other 4 cases.
One concludes that the total number of ways to arrange the sequences is $3\times268=804$, and the correct option is $D$.