Número de permutaciones de la palabra "PERMUTATION" de modo que ninguna dos vocales aparezcan juntas y ningún dos Ts aparezcan juntos

Question

¿De cuántas maneras podemos organizar las letras de la palabra "PERMUTATION" de modo que no haya dos vocales juntas y no haya dos Ts juntos?

Primero organicé las consonantes incluyendo una T de la siguiente manera:

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

Ahora en $6$ lugares con asterisco organizaré las vocales $A,E,I,O,U$ lo cual puede hacerse de $\binom{6}{5} \times 5!=6!$ maneras. Además, $P,R,M,N,T$ pueden organizarse por sí mismos de $5!$ maneras. Por lo tanto, el número total de palabras de diez letras ahora es de $5! \times 6!$.

Pero una $T$ debe colocarse en los once lugares de la palabra de diez letras de modo que no esté adyacente a la $T$ que ya está allí. Por lo tanto, la $T$ restante tiene $9$ maneras de colocarse.

Por lo tanto, la cantidad total de maneras es de $6! \times 5! \times 9$.

Pero mi respuesta no coincide con la respuesta del libro. Por favor corríjame.

Answer 1

Dado que hasta ahora hemos publicado dos respuestas diferentes (820,800 y 796,800), quizás se me pueda perdonar por aplicar maquinaria pesada.

Comenzamos reemplazando todas las vocales por Vs y preguntamos cuántas permutaciones hay de PVRMVTVTVVN en las que no hay dos letras adyacentes iguales. Según [1], la respuesta es $$N = \int_0^{\infty} e^{-t}\; \ell_1(t)^4 \;\ell_2(t) \; \ell_5(t) \; dt$$ donde $$\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 evalúa la integral como $N = 6,840$. Para responder al problema original, multiplicamos por $5!$ para tener en cuenta todas las formas de reemplazar las cinco Vs con las cinco vocales distintas: $$5! \; N = 820,800$$

[1] Teorema 2.1 en "Contando palabras con series de Laguerre" por Jair Taylor, The Electronic Journal of Combinatorics 21(2), 2014.

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

Answer 2

$\require{cancel}$

$\bcancel{* P * R * M * T * T * N *}$

$\bcancel{- Primero permuta las consonantes en 6!/2!= 360 formas}$

$\bcancel{En \frac{5}{\binom62} = \frac13 casos, las T's estarán juntas}$

$\bcancel{- Elige y coloca una vocal entre las T's de 5 formas, y las otras cuatro en 6\cdot 5\cdot 4\cdot3 = 1600 formas}$

$\bcancel{- Para las otras \frac23 lugares, coloca las vocales en 7\cdot6\cdot5\cdot4\cdot3 =2520 formas}$

$\bcancel{- Juntando las piezas, 360[\frac13\cdot 1600 + \frac23\cdot 2520] = 796800}$

---

Al revisitar la pregunta por casualidad después de $7$ años, me sorprende ver que mi respuesta publicada es incorrecta, aunque el error es misterioso

Pero no puedes discutir con los polinomios de Laguerre, así que decidí contrarrestar los polinomios de Laguerre con palabras de Smirnov, que son palabras en las que no hay letras idénticas juntas.

Aquí, agruparé todas las vocales como $V$, y usando la fórmula para palabras de Smirnov, extraigo el coeficiente requerido

$[P^1R^1M^1N^1T^2V^5]$ en

$\left(1-\frac{p}{1+p}-\frac{r}{1+r}-\frac{m}{1+m}-\frac{n}{1+n}-\frac{t}{1+t} -\frac{v}{1+v}\right)^{-1}= 6840$

Pero en realidad las $V's$ son $5$ vocales distintas, así que multiplicando por $5!$ obtenemos la respuesta correcta de $\color{blue}{820,800}$

Answer 3

Calcular todas las opciones sin restricción de $TT$ y restar las opciones con dos T juntos.

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

Enfoque ligeramente diferente:

Agregar 2 espacios $[]$ como vocales. Ahora debemos iterar las vocales y consonantes, obteniendo las mismas secuencias que antes después de eliminar los espacios para tener una sola palabra.

Dado que $T$ y $[]$ son duplicados, tenemos $7!/2 * 6!/2$ soluciones.

Sin embargo, tenemos que restar los patrones $T[]T$ para evitar dos $T$ juntos. Los patrones $T[]T$ pueden comenzar en 5 lugares, y podemos permutar aleatoriamente 4 consonantes y 6 vocales para completar el resto de la secuencia de iteración, así que restamos $5*4!*6!$.

Esta solución también da como resultado $820800$, así que debo quedarme con mi solución.

Answer 4

La palabra PERMUTACIÓN tiene once letras, de las cuales seis son consonantes y cinco son vocales. Primero vamos a organizar las consonantes, luego colocaremos las vocales. Consideraremos dos casos, dependiendo de si las Ts están separadas o juntas en la disposición de las consonantes.

Caso 1: Vamos a organizar las seis consonantes de forma que las Ts estén separadas.

Hay $4!$ de las consonantes P, R, M, N. Esto crea cinco espacios en los que colocar las Ts. $$\square C_1 \square C_2 \square C_3 \square C_4 \square$$ Para asegurar que las Ts estén separadas, debemos elegir dos de estos cinco espacios en los que colocar las $T$, lo cual se puede hacer de $\binom{5}{2}$ maneras. Ahora tenemos siete espacios en los que colocar las vocales. $$\square C_1 \square C_2 \square C_3 \square C_4 \square C_5 \square C_6 \square$$ Para asegurar que las vocales estén separadas, debemos elegir cinco de estos siete espacios en los que colocar una vocal, lo cual se puede hacer de $\binom{7}{5}$ maneras. Las cinco vocales se pueden organizar en los espacios seleccionados de $5!$ maneras. Por lo tanto, hay $$4!\binom{5}{2}\binom{7}{5}5!$$ tales disposiciones.

Caso 2: Vamos a organizar las seis consonantes de forma que las Ts estén juntas.

Tenemos cinco objetos distintos que organizar: P, R, M, N, TT. Se pueden organizar de $5!$ maneras. Ahora que hemos organizado las seis consonantes, nuevamente tenemos siete espacios en los que colocar las cinco vocales. Para asegurar que las Ts estén separadas, debemos colocar una de las vocales entre las dos Ts. Para asegurar que las vocales estén separadas, también debemos colocar una vocal en cuatro de los seis espacios restantes, lo cual se puede hacer de $\binom{6}{4}$ maneras. Podemos organizar las cinco vocales en los cinco espacios seleccionados de $5!$ maneras. Por lo tanto, hay $$5!\binom{6}{4}5!$$ tales disposiciones.

Total: Dado que estos casos son mutuamente excluyentes y exhaustivos, el número de disposiciones admisibles es $$4!\binom{5}{2}\binom{7}{5}5! + 5!\binom{6}{4}5!$$