Number of permutations of the word “PERMUTATION”

Question

In how many ways we can arrange the letters of the word "PERMUTATION" such that no two vowels occur together and no two T's occur together.

I first arranged consonants including one T as below:

$*P*R*M*T*N*$

Now in 6 star places i will arrange the vowels $A,E,I,O,U$ which can be done in $\binom{6}{5} \times 5!=6!$ ways. Also $P,R,M,N,T$ can themselves arrange in $5!$ ways. Hence total number of ten letter words now is $5! \times 6!$.

But one $T$ should be placed in eleven places of the ten letter word such that it should not be adjacent to $T$ which is already there. hence the remaining $T$ has $9$ ways to place.

hence total ways is $6! \times 5! \times 9$.

But my answer is not matching with book answer. please correct me

Answer 1

* P * R * M * T * T * N *

• First permute the consonants in $6!/2!= 360 $ ways

  In $\frac{5}{\binom62} = \frac13$ cases, the T's will be together

• Choose and place one vowel between the $T's$ in $5$ ways,
  and the balance four in $6\cdot 5\cdot 4\cdot3 = 1600$ ways

• For the balance $\frac23$ place the vowels in $7\cdot6\cdot5\cdot4\cdot3 =2520$ ways

• Putting the pieces together, $360[\frac13\cdot 1600 + \frac23\cdot 2520] = 796800$

Answer 2

Calculate all options without $TT$ restriction and subtract the options with two T's together.

$$ 6!/2! * 7 * 6 * 5 * 4 * 3 - 5! * 6*5*4*3*2 = 820800 $$

Slightly different approach:

Add 2 spaces $[]$ as vowels. We must now iterate vowels and consonants, yielding the same sequences as before after dropping the spaces to have a single word.

Since $T$ and $[]$ are duplicate, we have $7!/2 * 6!/2$ solutions.

However, we have to subtract $T[]T$ patterns to prevent two $T$'s together. $T[]T$ patterns can start at 5 places, and we can randomly permute 4 consonants and 6 vowels to fill the rest of the iterating sequence, so subtract $5*4!*6!$.

This solution also results in $820800$, so I have to stick to my solution.

Answer 3

Given that we have two different answers posted thus far (820,800 and 796,800), perhaps I can be forgiven for applying heavy machinery.

We start by replacing all the vowels with Vs and ask how many permutations there are of PVRMVTVTVVN in which no two adjacent letters are equal. According to [1], the answer is $$N = \int_0^{\infty} e^{-t}\; \ell_1(t)^4 \;\ell_2(t) \; \ell_5(t) \; dt$$ where $$\begin{align} \ell_1(t) &= t\\ \ell_2(t) &= \frac{1}{2} t^2 - t\\ \ell_5(t) &= \frac{1}{120}t^5 -\frac{1}{6}t^4 +t^3 -2t^2 + t\\ \end{align}$$

Mathematica evaluates the integral as $N = 6,840$. To answer the original problem, we multiply by $5!$ to account for all the ways of replacing the five Vs with the five distinct vowels: $$5! \; N = 820,800$$

[1] Theorem 2.1 in "Counting words with Laguerre series" by Jair Taylor, The Electronic Journal of Combinatorics 21(2), 2014.

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p1