Encontrar el número de permutaciones de $\{1,\cdots,6\}$ que no contienen 3 enteros consecutivos.

Question

Intenté encontrar el número de permutaciones de $\{1,\cdots,6\}$ que no contienen

las cadenas 123, 234, 345 o 456 utilizando el siguiente método,

y me gustaría saber por qué este método no da la respuesta correcta.

(En particular, ¿qué permutaciones cuenta incorrectamente?)

---

Tome el número total de permutaciones y luego reste las que tienen 3 enteros consecutivos, vuelva a sumar las que tienen 4 enteros consecutivos, reste las que tienen 5 enteros consecutivos, y finalmente sume la única permutación con todos los dígitos consecutivos para obtener

$6!-4\cdot4!+3\cdot3!-2\cdot2!+1\cdot1!=720-96+18-4+1=\color{blue}{639}$ .

Answer 1

Parece muy difícil responder a esta pregunta utilizando la GPIE. Por lo tanto, cuente el número de permutaciones para casos distintos y utilice la simetría cuando sea posible.

Dejemos que $R_n$ sea el conjunto de todas las permutaciones que tienen un recorrido máximo de $n$ dígitos consecutivos en orden pero que no tienen otra serie disjunta de tres o más (hay una permutación que tiene dos series disjuntas de tres dígitos consecutivos), y $R_{3,3}$ sea el conjunto de todas las permutaciones que tienen dos tramos disjuntos de tres.

Dejemos que $N(\ldots,x,y,z,\ldots)$ sea el número de permutaciones que tienen $(x,y,z)$ en orden a partir de cualquier dígito de la permutación, y $N(\ast,x,y,z,\tilde{}m,\ldots)$ sea el número de permutaciones que tienen $(x,y,z)$ (a partir del segundo dígito) seguido de cualquier cosa que no sea $m$ y un primer dígito no restringido.

Entonces $$\begin{align} N(R_3) &= N(\ldots,1,2,3,\ldots) + N(\ldots,2,3,4,\ldots) + N(\ldots,3,4,5,\ldots) + N(\ldots,4,5,6,\ldots) \\ &= 2N(\ldots,1,2,3,\ldots) + 2N(\ldots,2,3,4,\ldots)\qquad(\text{by symmetry}) \end{align}$$

y $$\begin{align} N(\ldots,1,2,3,\ldots) &= N(1,2,3,\tilde{}4,\ast,\ast) + N(\ast,1,2,3,\tilde{}4,\ast) + N(\ast,\ast,1,2,3,\tilde{}4) + (N(\ast,\ast,\ast,1,2,3) - N(4,5,6,1,2,3)) \\ &= 4 + 4 + 4 + (6-1) \\ &= 17 \end{align}$$

y $$\begin{align} N(\ldots,2,3,4,\ldots) &= N(2,3,4,\tilde{}5,\ast,\ast) + N(\tilde{}1,2,3,4,\tilde{}5,\ast) + N(\ast,\tilde{}1,2,3,4,\tilde{}5) + N(\ast,\ast,\tilde{}1,2,3,4) \\ &= 4 + 3 + 3 + 4 \\ &= 14 \end{align}$$

Así que $\boxed{N(R_3) = 2(17) + 2(14) = 62}$

Entonces $$\boxed{N(R_{3,3}) = N(4,5,6,1,2,3) = 1}$$

También $$\begin{align} N(R_4) &= N(\ldots,1,2,3,4,\ldots) + N(\ldots,2,3,4,5,\ldots) + N(\ldots,3,4,5,6,\ldots) \\ &= 2N(\ldots,1,2,3,4,\ldots) + N(\ldots,2,3,4,5,\ldots)\qquad(\text{by symmetry}) \end{align}$$

donde $$\begin{align} N(\ldots,1,2,3,4,\ldots) &= N(1,2,3,4,\tilde{}5,\ast) + N(\ast,1,2,3,4,\tilde{}5) + N(\ast,\ast,1,2,3,4) \\ &= 1 + 1 + 2 \\ &= 4 \end{align}$$

y $$\begin{align} N(\ldots,2,3,4,5,\ldots) &= N(2,3,4,5,\tilde{}6,\ast) + N(\tilde{}1,2,3,4,5,\tilde{}6) + N(\ast,\tilde{}1,2,3,4,5) \\ &= 1 + 1 + 1 \\ &= 3 \end{align}$$

Así que $\boxed{N(R_4) = 2(4) + 3 = 11}$

También $$\begin{align} N(R_5) &= N(\ldots,1,2,3,4,5,\ldots) + N(\ldots,2,3,4,5,6,\ldots) \\ &= 2N(\ldots,1,2,3,4,5,\ldots)\qquad(\text{by symmetry}) \end{align}$$

donde $$\begin{align} N(\ldots,1,2,3,4,5,\ldots) &= N(1,2,3,4,5,\tilde{}6) + N(\ast,1,2,3,4,5) \\ &= 0 + 1 \\ &= 1 \end{align}$$

Así que $\boxed{N(R_5) = 2(1) = 2}$

Finalmente $\boxed{N(R_6) = 1}$

Así que el número de permutaciones sin tres dígitos en orden viene dado por: $$\begin{align} 6! - N(R_3) - N(R_{3,3}) - N(R_4) - N(R_5) - N(R_6) &= 720 - 62 - 1 - 11 - 2 - 1 \\ &= 643 \end{align}$$

Answer 2

Dejemos que $A_i$ sea el conjunto de permutaciones que contienen la cadena $i, i+1, i+2$ para $1\le i\le 4$ y

dejar $S$ sea el conjunto de todas las permutaciones de $\{1,\cdots,6\}$ .

Entonces $\displaystyle\big|A_1^c\cap\cdots\cap A_4^c\big|=\big|S\big|-\sum_{i}\big|A_i\big|+\sum_{i<j}\big|A_i\cap A_j\big|-\sum_{i<j<k}\big|A_i\cap A_j\cap A_k\big|+\big|A_1\cap\cdots\cap A_4\big|$

$\displaystyle\hspace{1.4 in}=6!-4\cdot4!+\big(3\cdot3!+3\cdot2!\big)-\big(2\cdot2!+2\cdot1\big)+1=643.$

---

Su método cuenta cada una de las siguientes permutaciones dos veces, en lugar de sólo una,

cuando se cuenta el número de permutaciones en el complemento:

$\hspace{.5 in}123456, \;\;612345,\;\;234561,\;\;456123$