Contar las permutaciones de $\{1,2,...,7\}$ sin 4 números consecutivos - ¿hay una manera inteligente y elegante de hacerlo?

Question

Este es un problema que he resuelto:

Contar las permutaciones de $\{1,2,...,7\}$ sin 4 números consecutivos (por ejemplo, 1,2,3,4).

Así que lo hice un poco a la fuerza bruta - dejar que $A_i$ sea el conjunto de permutaciones de $[7]$ , donde $i,i+1,i+2,i+3$ son números consecutivos. Sólo $A_1,A_2,A_3,A_4$ son no vacíos, por lo que podemos utilizar el principio de inclusión-exclusión. Así, si $S_0$ es el conjunto de todas las permutaciones de $[7]$ y $S_j=\sum_{i_1\leq i_2 \leq ...\leq i_j} |A_{i_1} \cup A_{i_2} \cup ... \cup A_{i_j}|$ , entonces podemos contar fácilmente que $S_1 = 4 * 4!$ (elija qué número inicia el bloque de 4 números consecutivos (4 opciones), luego permute este bloque y 3 números restantes en $4!$ formas), $S_4 = 1$ y para $S_2, S_3$ He utilizado la fuerza bruta: he enumerado todos los posibles arreglos de conjuntos y los he contado a mano (sólo hay $\binom{4}{2}+\binom{4}{3}$ casos a considerar). Entonces la respuesta es $S_0-S_1+S_2-S_3+S_4$ por el principio de inclusión-exclusión.

La pregunta es: ¿se puede omitir la parte de fuerza bruta de la solución? ¿Hay alguna forma más inteligente de hacerlo?

Answer 1

He aquí otra forma semi-brutal de contar el número de permutaciones que incluyen una serie de cuatro números consecutivos.

Obsérvese que para cualquier permutación $abcdefg$ con una racha de cuatro números consecutivos, el número del medio $d$ deben participar en la carrera. Deje que $n_i$ sea el número de tales permutaciones en las que el número medio es $i$ , para $i=1$ a $7$ . Una modesta cantidad de fuerza bruta da

$$n_1+n_2+n_3+n_4+n_5+n_6+n_7=6+10+14+18+14+10+6=78$$

Una comprobación de cordura es que $n_{8-i}=n_i$ . Esto se debe a que al restar cada número de una permutación a $8$ y luego escribir la permutación hacia atrás preserva las ejecuciones consecutivas.

Para demostrar que no se trata de fuerza bruta, he aquí la respuesta correspondiente a las permutaciones de los números $1$ a $9$ con una carrera de cinco números consecutivos, presentados de forma sugerente:

$$4!+(4!+1\cdot3\cdot3!)+(4!+2\cdot3\cdot3!)+(4!+3\cdot3\cdot3!)\\+(4!+4\cdot3\cdot3!)\\+(4!+3\cdot3\cdot3!)+(4!+2\cdot3\cdot3!)+(4!+1\cdot3\cdot3!)+4!$$

Debería estar razonablemente claro que esto conduce a una fórmula sencilla para el número de permutaciones de los números $1$ a $2n-1$ con una carrera de $n$ números consecutivos:

$$(n^2-n+1)(n-1)!$$

Answer 2

Los casos de fuerza bruta se calculan exactamente igual que el caso que has calculado correctamente: para encontrar el número de formas de permutar $n$ números con una racha de $k$ , elija el número inicial de la tirada en $n-k+1$ formas, y luego permutar la posición de la carrera y el resto $n-k$ números en $(n-k+1)!$ formas. Es necesario incluir/excluir ejecuciones de $4$ o mayor. Así que el resultado es $$ 7! - 4\cdot 4! + 3\cdot 3! - 2\cdot 2! + 1\cdot 1!=7!-96+18-4+1=7!-81. $$

---

Actualización: El simple razonamiento de inclusión/exclusión anterior no funciona del todo, porque hay que excluir los casos en los que hay dos carreras de longitud $k$ ... no los casos en que hay una carrera de longitud $k+1$ ... de la enumeración de los casos con un recorrido de longitud $k$ . Esto es diferente porque puede tener dos carreras de longitud $k$ que se superponen en cualquier número de posiciones de $2k-n$ a $k-1$ (suponiendo que $2k-n\ge 1$ ), y un solapamiento de longitud $m$ produce una carrera de longitud $2k-m$ . Fijación de $n$ suficientemente grande, y dejando $N_k$ sea el número de formas de organizar $n$ elementos con un recorrido de al menos $k$ tenemos $N_n=1\cdot 1!$ y $$N_{n-1}=2\cdot 2! - N_n = 2\cdot 2! - 1\cdot 1! = 3,$$ y $$ N_{n-2}=3\cdot 3! - N_{n-1} - N_{n} = 3\cdot 3! - (2\cdot 2! - N_n) - N_n \\ = 3\cdot 3! - 2\cdot 2!=14. $$ Siguiente, $$ N_{n-3}=4\cdot 4! - N_{n-2} - N_{n-1} - N_{n} = 4\cdot 4! - (3\cdot 3! - N_{n-1} - N_{n}) - N_{n-1} - N_{n} \\ = 4\cdot 4! - 3\cdot 3! = 78. $$ Y así sucesivamente. Para $2k-n\ge 1$ el número de permutaciones de $n$ elementos con un recorrido de longitud $k$ viene dada por $(n-k+1)\cdot(n-k+1)!-(n-k)\cdot(n-k)!$ . Para $2k\le n$ por otro lado, existe la complicación adicional de que también se pueden tener dos recorridos no superpuestos de longitud $k$ que no están unidos en una sola tirada de longitud $2k$ y estos casos también hay que restarlos. Por ejemplo, para $n=6$ y $k=3$ , se obtiene $4\cdot 4! - 3\cdot 3!-1=77$ , donde el final $1$ proviene del caso único $456123$ .

Answer 3

Puede ser que encuentres este camino menos brutish , aunque apenas elegante ¡!

1. Mira sólo los 2 extremos de la secuencia (llámalos L y R) y cuántos números son eliminado para crear bloques de números consecutivos, y contaremos por bloques de exactamente 4,5,....7.

2. Contaremos bloques de exactamente 4 (lo que supondrá la mayor dificultad, e ilustrará el proceso con mayor claridad). Obsérvese que estos bloques pueden ser de dos tipos: bloques iniciales/finales "inseguros" en un solo extremo, y bloques intermedios "inseguros" en ambos extremos.

3. Bloque 1234, el lado L es seguro, el lado R no: Por lo tanto, sólo 2 de los números eliminados pueden colocarse adyacentes a R: 3-0 colocado L-R de 3 maneras, un poco de pensamiento mostrará que 2-1 o 1-2 y 0-3 tendrán cada uno 4 maneras de colocación (total 18). Lo mismo ocurre con el bloque 5678. [Hay un patrón ¡a toda esta locura! ]

4. Bloque 2345 (inseguro en ambos extremos): Se puede ver fácilmente que habrá 4 colocaciones cada una para 3-0 o 0-3, y 3 colocaciones cada una para 2-1 o 1-2 (total 14). Lo mismo ocurre con el bloque 3456

5. Así que para bloques de exactamente 4, habrá $(18+14)*2$ = 64 formas.

6. Contar para bloques de 5, 6 y 7 es relativamente trivial, 11,2 y 1 respectivamente.

7. Por lo tanto, la respuesta final = 64+11+2+1 = 78.