How many arrangements of the letters A, B, C, D, E, F and 10 Xs are there if none of the letters A − F can be next to each other?

Question

I am currently working on a question which I disagree with the given solution.

How many arrangements of the letters A, B, C, D, E, F and 10 copies of the letter X are there (i.e. of A, B, C, D, E, F, X, X, X, X, X, X, X, X, X, X) if we insist that none of the letters A − F can be next to each other?

$\textbf{Given Solution}:$

There are two cases: the arrangement ends with a non-X or an X.

In case (1), we create new symbols "XA", "XB" ..., "XF", and arrange these and the remaining four X’s (ten total symbols to arrange). This will force that none of the A-F are actually next to each other, and as long as we pick on of the "XA",...,"XF" to be at the end of the arrangement, we will have satisfied the requirement. So we count the total minus the complement: the arrangements where an X is fixed the end, giving $\frac{10!}{4!} − \frac{9!}{3!}$

(the latter count given by putting an X at the end, then arranging the remaining 9 symbols.)

In case (2), this time we make symbols "AX", "BX",...,"FX", and arrange these and the remaining four X’s. This time any symbol among these ten can be at the end, so we have no extra requirement to satisfy: $\frac{10!}{4!}$

QED

$\textbf{My Solution:}$

Consider the fact that, for all the 6 letters A-F, we can put any one of the letters A-F between any of the 10 X's. That is, we can put the letters A-F to replace 6 of the underscores of the string "_X_X_X_X_X_X_X_X_X_X_X_".

For A, we have 11 spots to pick, for B, we have 10 spots to pick and so on. In total, we can replace 6 undescores of our string with the letters A-F in $\frac{11!}{(11-6)!}$ different ways. Furthermore, we can create a bijection between the ways we can replace the 6 underscores of the string, and the arrangements of the original 16 letters such that no A-F are next to each other. For example, we have:

AXBXCXDXEXFX_X_X_X_X_, which corresponds to the arrangement AXBXCXDXEXFXXXXX

or

_X_X_X_X_AXBXCXDXEXFX, which corresponds to the arrangement XXXXAXBXCXDXEXFX

and so on.

QED

I was wondering if my solution is correct (or not) and if the given solution is incorrect (or not). Since the given solution does not consider some cases such as AXBXCXDXEXXXXXXF. This is a case where none of A-F are next to each other, but it does not end with an X, so it is not counted in case 1. It does not have the symbol "FX", so it cannot be in case 2 either.

Answer 1

Yes, you are definitely right and your example $AXBXCXDXEXXXXXXF$ summarizes your argument really well (Notice that there are lots of examples like this one so given solution is missing some of the orderings). And if we compute the exact result in given solution, it is $241920$. However in your proposed solution, it is $332640$. So you are right to be suspected that there might be some missing cases.

On the other hand, your proposed solution has neither overcounting cases nor the missing ones. That is also the most common way of solving these kind of problems. I think you detected the issue in given solution well. Shortly, your proposed solution is correct.

Answer 2

Your solution is absolutely fine and correct and can be verified using star and bars too.

First we permute the six letters from A to F. This can be done in $6!$ ways.

Now consider any one permutation of those. For example we consider $ABCDEF$ .

Let $x_1$ be the number of $X's$ placed before A, $x_2$ be the number of $X's$ placed between A and B, $x_3$ be the number of $X's$ placed between B and C,....., $x_7$ be number of $X's$ placed after F. We know that $x_2,x_3,x_3,....,x_6\ge 1$

Hence by star and bars method we need to find non negative integral solutions of $$x_1+x_2+x_3+x_4+x_5+x_6+x_7=5$$ Which is equal to $\binom {11}{6}$

Hence our answer will be $$\binom {11}{6}.6!$$

Answer 3

As both @ArsenBerk and @Manthanein have stated, your solution is correct.

Why is the given solution incorrect?

If you examine case 1, notice that the first letter must be an X. If you examine case 2, notice that the last letter must be an X. Therefore, the authors did not consider the possibility that neither the first nor the last letter was an X.

How many such arrangements are there?

Using your method, we arrange ten Xs in a row, which creates $11$ spaces.

$$\square X \square X \square X \square X \square X \square X \square X \square X \square X \square X \square$$

To ensure that both ends of the row are occupied by a letter other than X and that no two of the letters A, B, C, D, E, F are consecutive, we must choose the spaces at both ends and four of the nine spaces between successive Xs in which to place the six letters A, B, C, D, E, F. We can do this in $\binom{9}{4}$ ways. Therefore, the number of arrangements that begin and end with a letter other than X in which no two of the letters A, B, C, D, E, F are consecutive is $$\binom{9}{4}6!$$ If we add these cases to the ones considered by the authors, we obtain $$\frac{10!}{4!} - \frac{9!}{3!} + \frac{10!}{4!} + \binom{9}{4}6! = \binom{11}{6}6!$$ as you can check.