Counting the number of arrangements

Question

Question: The five vowels— A, E, I, O, U—along with 15 X’s are to be arranged in a row such that no X is at an extreme position. Also, between any two vowels there must be at least 3 X’s. Find the number of ways in which this can be done.

My Approach: We consider a setup as follows:

$A\;|1|\;E\;|2|\;I\;|3|\;O\;|4|\; U$

The containers marked $|1|, \; |2| , \; \cdots $ contain 3 $X$'s for the time being. Thus we have 12 $X$s assigned, and only 3 left to distribute among the 4 containers.

The three $X$s can be distributed in 4 containers in $\sum_{i=1}^3$${4}\choose{i}$$=4+6+4=14$ ways.

(This is because we can split $3$ in four parts as $1|1|1|0$ or $2|1|0|0$ or $3|0|0|0 $. Then we assign those to the four containers accordingly. For example, the first case of $1|1|1|0$ involves assigning the $0$ value to any one of the 4 containers, and the rest get one $X$ each. This can be done in $4\choose1$ ways. Similarly others follow. )

The vowels can be shuffled around, keeping the $X$s fixed, in $5!$ ways.

So, the answer comes out to be $14*5!=1680$ ways.

But my answer turns out to be wrong.

Any help in finding the error of my ways is highly appreciated.

Answer 1

Your $2|1|0|0$ can be arranged in $12$ ways, not $6$

Answer 2

The best way to allocate the spare $X$s is through stars-and-bars, allocating the indistinguishable $X$s into four categories by adding dividers (representing a category change) and deciding where to place those. For example:

$$XX\mid{}\mid{} X \mid{} \equiv 2,0,1,0$$

Thus we are positioning $3$ items in a $6$-length string (consisting of $3$ $X$s and $3$ dividers), $\binom 63 = 20$.

---

$\fbox{$XX$}\fbox{$\phantom X$}\fbox{$X$}\fbox{$\phantom X$}$ is represented as $\fbox{$XX\mid{}\mid{} X \mid{} $}$ if that makes the roles of divider elements any clearer.

With the same problem but only requiring $2$ $X$s between vowels, we would have $7$ spare $X$s and an example solution could look like $XX\mid{XXX}\mid{} \mid{XX} $, positioning three dividers in (now) a $10$-length string, $\binom {10}{3} = 120$

Answer 3

Forgetting about X's, vowels have $5!$ distinct permutations. So you have $5!$ options. For each permutation like $A, E, I, O, U$, you have to place X's in between. $A \langle x_1\rangle E \langle x_2\rangle I \langle x_3\rangle O \langle x_4\rangle U$ is the representation of your string where the permutation of vowels is $A, E, I, O, U$ and $\langle x_i\rangle$'s denote the number of $X$'s between two vowels. So: $x_1+x_2+x_3+x_4=15$ since we have $15$ $X$'s. On the other hand between every two consecutive vowels, there must exist at least three $X$'s, so: $x_i\geq 3$. Now let $y_i=x_i-3$. Therefore, $y_1+y_2+y_3+y_4=3$ and $y_i\geq0$. Now you have to find out how many answers do we have for the above equation: there are ${4+3-1}\choose{4-1}$ $=$ ${6}\choose{3}$ $=20$ different answers. So: you have $5!$ cases for the permutations and $20$ for the equations, so there are $5!.20 =2400$ different strings.