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$
2
  • $\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$ Mar 9, 2016 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$ Mar 9, 2016 at 7:17

3 Answers 3

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$
2
  • $\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, 2016 at 8:01
  • $\begingroup$ I have refined it, I believe it should be ok now. $\endgroup$ Mar 9, 2016 at 8:09
4
$\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$
2
  • $\begingroup$ That's a very interesting post $\endgroup$ Mar 14, 2016 at 3:44
  • $\begingroup$ I love this, only partially because it showed me right ;) $\endgroup$
    – Pieter21
    Aug 31, 2016 at 7:13
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$
2
  • $\begingroup$ I think some options with two $T's$ together from your first term are inflating the count. $\endgroup$ Mar 9, 2016 at 19:13
  • $\begingroup$ @trueblueanil, I added a slightly different approach, and I have to stick to my result. $\endgroup$
    – Pieter21
    Mar 10, 2016 at 8:34

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.