5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ By starting with that arrangement of consonants, without considering the placement of the second T, you miss out on certain arrangements that should be made possible, for instance, P∗T∗R∗M∗T∗N∗ $\endgroup$ – Quinn Greicius Mar 9 '16 at 7:05
  • $\begingroup$ Actually, that starting arrangement doesn't really throw you off, but when you consider adding the second T to the mix, recognize that any of the other letters (except the first T) can also take that place (as in my example above), and adjust accordingly. What is the answer given in the book? $\endgroup$ – Quinn Greicius Mar 9 '16 at 7:17
4
$\begingroup$

* 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$

$\endgroup$
  • $\begingroup$ I like the approach but I think the solution is not integral (you divide by 11), and I don't understand why this doesn't work. $\endgroup$ – Pieter21 Mar 9 '16 at 8:01
  • $\begingroup$ I have refined it, I believe it should be ok now. $\endgroup$ – true blue anil Mar 9 '16 at 8:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think some options with two $T's$ together from your first term are inflating the count. $\endgroup$ – true blue anil Mar 9 '16 at 19:13
  • $\begingroup$ @trueblueanil, I added a slightly different approach, and I have to stick to my result. $\endgroup$ – Pieter21 Mar 10 '16 at 8:34
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That's a very interesting post $\endgroup$ – Umesh shankar Mar 14 '16 at 3:44
  • $\begingroup$ I love this, only partially because it showed me right ;) $\endgroup$ – Pieter21 Aug 31 '16 at 7:13

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.