Encuentra el número de reordenamientos de la cadena 12345 en los que no aparece ninguna de las secuencias 12, 23, 34 y 45.

Question

Mi intento: Que $A_{1}$ denotan donde ocurre el 12, $A_{2}$ denotan el lugar donde se encuentra el 23, $A_{3}$ denotan el lugar donde se encuentra el 34, $A_{4}$ denotan el lugar donde se produce el 45.

| $A_{1} \cup A_{2} \cup A_{3} \cup A_{4}$ |= | $A_{1}$ |+| $A_{2}$ |+| $A_{3}$ |+| $A_{4}$ |-(| $A_{1}A_{2}$ |+| $A_{1}A_{3}$ |+| $A_{1}A_{4}$ |+| $A_{2}A_{3}$ |+| $A_{2}A_{4}$ |+| $A_{3}A_{4}$ |)+| $A_{1}A_{2}A_{3}$ |+| $A_{1}A_{2}A_{4}$ |+| $A_{1}A_{3}A_{4}$ |+| $A_{2}A_{3}A_{4}$ |-| $A_{1}A_{2}A_{3}A_{4}$ |

No sé si estoy haciendo este escrito o no. He intentado pegar los 12, 23, 34 y 45 pero no creo que sea correcto. ¡El total de formas en que se puede hacer esto sin restricciones es |U|=5!

La respuesta real es: ¡5!-[96-3+8-1]=53.

Si alguien puede decirme cómo obtener esta respuesta sería excelente.

Answer 1

Sí, su enfoque es correcto. Tenga en cuenta que $|A_i|=4\cdot 3!=24$ , $|A_iA_j|=6$ , $|A_iA_j A_k|=2$ y $|A_1A_2A_3A_4|=1$ . Por lo tanto, $|A_{1} \cup A_{2} \cup A_{3} \cup A_{4}|$ es igual a $$\binom{4}{1}\cdot |A_i|-\binom{4}{2}\cdot |A_iA_j|+\binom{4}{3}\cdot |A_iA_j A_k|-\binom{4}{4}\cdot |A_1A_2A_3A_4|.$$ lo que implica que el número de esas permutaciones es $|U|-|A_{1} \cup A_{2} \cup A_{3} \cup A_{4}|$ : $$5!-(4\cdot 24-6\cdot 6+4\cdot 2-1)=120-(96-36+8-1)=53.$$

Enfoque alternativo. Dejemos que $p(n)$ sea el número de permutaciones de $[1,\dots,n]$ que no tiene ninguna subcadena $[k,k+1]$ con $1\leq k\leq n-1$ . Entonces $p(1) = 1$ , $p(2) =1$ y, para $n\geq 2$ satisface la recurrencia $$p(n+1) = n p(n) + (n-1)p(n-1).$$ Por lo tanto, $p(3)=2p(2)+p(1)=3$ , $p(4)=3p(3)+2p(2)=11$ y $$p(5)=4p(4)+3p(3)=44+9=53.$$

Answer 2

Este es básicamente el enfoque correcto. Sólo hay que calcular los tamaños de las distintas intersecciones. Un par de ejemplos. Pensemos en $A_2\cap A_3$ . Se trata de permutaciones en las que $2$ es seguido por $3$ y $3$ por $4$ . Se trata, pues, de arreglos de "bloques", $1$ , $234$ y $5$ Así que $|A_2\cap A_3|=3!$ de estos. Por otro lado $A_2\cap A_4$ cuenta disposiciones de los bloques $1$ , $23$ y $45$ así que de nuevo $|A_2\cap A_4|=3!$ etc.