¿Cuántas permutaciones de$\{1, \ldots, n\}$ existen de tal manera que ninguna de ellas contenga$(i, i+1)$ (como una secuencia) para$i \in {1,...,(n-1)}$?

Question

¿Cuántas permutaciones de$\{1, \ldots, n\}$ existen de tal manera que ninguna de ellas contenga$(i, i+1)$ (como una secuencia) para$i \in {1,...,(n-1)}$?

Lo primero que me viene a la mente es encontrar todos los que tienen$(i, i+1)$ y luego restarlos de todas las permutaciones. Pero entonces podemos tener$(i, i+1, i+2)$ que restamos dos veces, una vez en$(i, i+1)$ y una vez en$(i+1, i+2)$. Y así sucesivamente para$3$ y más. ¿Cómo calculo esto?

Answer 1

Supongamos que hay $p_n$ permutaciones de la primera $n$ enteros sin prohibido pares

Luego hay $(n-1)p_{n-1}$ permutaciones con exactamente una prohibido par como usted ha $n-1$ pares de tales enteros y el resto de la permutación no debe contener ellos

Así que cuando usted consigue un nuevo entero $n+1$ puede

• poner en el comienzo de una permutación de la primera $n$ enteros sin prohibido pares: $p_n$ posibilidades
• ponemos inmediatamente después de cualquiera de los números enteros de distinto $n$ en una permutación de la primera $n$ enteros sin prohibido pares: $(n-1)p_n$ posibilidades
• puso en el centro de la prohibida la par de una permutación con exactamente una prohibido par: $(n-1)p_{n-1}$ posibilidades

Que le da la recurrencia

$$p_{n+1} = np_n+(n-1)p_{n-1}$$

y como Rebecca J. Piedras dice, este es OEIS A000255 offset

Answer 2

Si tomamos por ejemplo una permutación en $\{1,\ldots,n\}$ y eliminar $n$ obtenemos:

• una permutación de $\{1,\ldots,n-1\}$ sin $(i,i+1)$ larga, o

• una permutación de $\{1,\ldots,n-1\}$ con exactamente un $(i,i+1)$ larga, que se produce cuando la secuencia original tenía un $(i,n,i+1)$ larga.

  En este caso, si que en lugar de eliminar el $n$ $i+1$ a partir de esta secuencia y re-etiquetar los elementos de $e \geq i+2$$e-1$, se obtiene una permutación de $\{1,\ldots,n-2\}$ sin $(i,i+1)$ larga. (Tenga en cuenta que el elemento después de $i+1$ en la secuencia no puede ser $i+2$, o la secuencia original contenía una $(i+1,i+2)$ larga.)

Por el contrario, hemos de construcción de estos en las siguientes maneras:

1. Dada una permutación de $\{1,\ldots,n-1\}$ sin $(i,i+1)$ larga, podemos insertar $n$, excepto directamente después de $n-1$, dando $n$ posibilidades.

2. Dada una permutación de $\{1,\ldots,n-2\}$ sin $(i,i+1)$ larga, podemos elegir un elemento $i$, aumento de los elementos de mayor que $i$$1$, e inserte $(n,i+1)$ después $i$; esto da $n-1$ posibilidades.

Tenga en cuenta que los métodos 1. y 2. arriba secuencias distintas.

Por lo tanto, el número de $f(n)$ de tales permutaciones satisface la relación de recurrencia $$f(n)=nf(n-1)+(n-1)f(n-2)$$ and we observe $f(1)=1$ and $f(2)=1$.

Este es Sloane del OEIS A000255, donde muchas de las fórmulas están en la lista, y comienza la secuencia: $$ 1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, 2467007773, \ldots $$

Answer 3

La inclusión-exclusión de inmediato los rendimientos

$$\sum_{p=0}^{n-1} {n-1\choose p} (-1)^p (n-p)!$$

que da la secuencia

$$1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457,\ldots$$

Los nodos de la poset aquí representan subconjuntos $P$ $[n-1]$ donde un elemento $q\in P$ indica que $[q,q+1]$ está presente en la permutación. Por lo tanto $P$ corresponde a las permutaciones donde $[q,q+1]$ es presente, con $q\in P$, y posiblemente más pares adyacentes. Por lo tanto sólo $P=\emptyset$ representa permutaciones sin consecutivos elementos adyacentes. Con el peso de ser $(-1)^{|P|}$ obtenemos el peso uno de estos. En la otra mano una permutación con exactamente $R\subseteq[n-1], R\ne\emptyset$ pares adyacentes se incluye en todos los los nodos de $P\subseteq R$, dando peso

$$\sum_{P\subseteq R} (-1)^{|P|} = \sum_{p=0}^{|R|} {|R|\elegir p} (-1)^p = 0,$$

la producción de cero. Queda por calcular la cardinalidad de la permutaciones representado por un nodo $P$ donde $|P|=p.$ Tenemos una lista de los pares de $[q,q+1]$ donde $q\in P$ en su orden, de la fusión adyacentes con los mismos valores (y la eliminación de los duplicados) para formar bloques, decir que hay un $m$ de ellos, con longitudes $l_1, l_2, \ldots l_m.$ Aquí podemos observar que $1\le m\le p.$ Tenemos por construcción que

$$l_1-1+l_2-1+\cdots+l_m-1 = |P|=p.$$

El número de elementos que se han eliminado de la $n$ disponible es

$$l_1+l_2+\cdots+l_m = p + m.$$ We put the $m$ bloques de vuelta en llegar

$$n-(p+m)+m = n - p$$

los componentes que luego podemos permutar, por lo tanto la conclusión de PASTEL.

Observación. Este problema apareció en el siguiente MSE enlace.