Número de permutaciones sin sucesión

Question

La cuestión es calcular el número de permutaciones $\pi\in S_n$ tal que $\pi(i+1)\neq\pi(i)+1$ para todos $1\leq i\leq n-1$ .

Answer 1

Consideremos la distribución uniforme en $S_n$ . Para cada $i$ en $\{1,2,\ldots,n-1\}$ , dejemos que $A_i$ denota el caso de que $\pi(i+1)=\pi(i)+1$ . Sea $A$ denotan la unión de los eventos $A_i$ . Se pregunta por el cardenal de $S_n\setminus A$ .

Por el principio de inclusión-exclusión , $$ \mathrm P(A)=\sum\limits_I(-1)^{|I|+1}\mathrm P(A_I), $$ donde la suma corre sobre cada subconjunto no vacío $I$ de $\{1,2,\ldots,n-1\}$ y $A_I$ denota la intersección de los eventos $A_i$ para $i\in I$ .

El conjunto $A_I$ de permutaciones tales que $\pi(i+1)=\pi(i)+1$ por cada $i\in I$ está en biyección (1) con $S_{n-|I|}$ por lo que $P(A_I)=(n-|I|)!/n!$ . Hay ${n-1\choose k}$ subconjuntos $I$ de $\{1,2,\ldots,n-1\}$ de tamaño $k$ por lo que $$ \mathrm P(A)=\sum\limits_{k=1}^{n-1}(-1)^{k+1}\frac{(n-k)!}{n!}{n-1\choose k}=\sum\limits_{k=1}^{n-1}(-1)^{k+1}\frac{n-k}{n}\frac1{k!}. $$ Finalmente, $$ |S_n\setminus A|=n!\cdot \mathrm P(S_n\setminus A)=n!-(n-1)!\cdot\sum\limits_{k=1}^{n-1}(-1)^{k+1}\frac{n-k}{k!}, $$ es decir, $$ |S_n\setminus A|=(n-1)!\cdot\sum\limits_{k=0}^{n-1}(-1)^{k}\frac{n-k}{k!}. $$ Nota

(1) Para ver esto, arregle $I$ y considerar una permutación $\pi'$ en $S_{n-|I|}$ . Sea $I'=\{i\in\{1,2,\ldots,n\}\mid i-1\notin I\}$ . Para cada $i\in I'$ , dejemos que $$ \pi(i)=\pi'(i)+|\{j\leqslant i-1\mid j\in I\}|. $$ Para completar la definición de $\pi$ , utiliza de forma recursiva la propiedad $\pi(i+1)=\pi(i)+1$ por cada $i\in I$ . Entonces la función $\pi'\mapsto\pi$ es una biyección de $S_{n-|I|}$ a $A_I$ .

Answer 2

Si, para alguna permutación $\pi$ , $\pi(i+1) = \pi(i)+1$ para exactamente $k$ valores de $i$ entonces digamos que $\pi$ tiene $k$ sucesiones . Sea $S_{n,k}$ denotan el número de permutaciones en $[n]$ con $k$ sucesiones. El PO está preguntando por el valor de $S_{n,0}$ que, para simplificar, vamos a llamar $S_n$ . La respuesta de Didier da una fórmula exacta para $S_n$ . Aquí hay una bonita recurrencia que puede ser de interés.

$S_n = (n-1)S_{n-1} + (n-2) S_{n-2}, \text{ } n \geq 3.\tag{1}$

Prueba : Se puede obtener esto de la fórmula de Didier, pero hagámoslo combinatoriamente. Toda permutación sin sucesiones en $[n]$ puede formarse bien por (a) la inserción de $n$ en una permutación sin sucesiones en $[n-1]$ en cualquier lugar que no sea después del elemento $n-1$ o (b) insertando $n$ en una permutación con una sucesión en $[n-1]$ entre los elementos sucesivos. Como lo primero puede hacerse en $n-1$ formas y la segunda de una manera, esto da como resultado $S_n = (n-1)S_{n-1} + S_{n-1,1}$ .

Ahora tenemos que demostrar que $S_{n,1} = (n-1)S_{n-1}$ . Supongamos que tenemos una permutación $\pi$ sin sucesiones en $[n-1]$ . Podemos construir $n-1$ permutaciones con una sucesión en $[n]$ de la siguiente manera: Primero, seleccione uno de los $n-1$ elementos en $\pi$ . Llama a este elemento $k$ . Utilizando la notación de una línea para $\pi$ para cada $j \geq k$ , dejemos que $j = j+1$ . A continuación, inserte el elemento $k$ antes del nuevo elemento $k+1$ . Esto nos da la sucesión $(k,k+1)$ . No hay sucesiones $(j,j+1)$ para cualquier $j > k$ o para cualquier $j < k-2$ porque el proceso anterior preserva (en el primer caso) o aumenta (en el segundo) la diferencia entre dos elementos consecutivos en una permutación que ya no tenía sucesiones. Tampoco tenemos la sucesión $(k-1,k)$ . O bien el elemento anterior a $k$ en $\pi$ era mayor que $k$ en cuyo caso aumentó en uno, o fue menor que $k$ en cuyo caso se mantuvo igual (y por lo tanto no produjo una sucesión porque $\pi$ no tiene sucesiones).

Por ejemplo, este proceso, aplicado a la permutación $15243$ (no hay sucesiones) produce, seleccionando sucesivamente 1, 2, 3, 4 y 5, las permutaciones $\color{red}{12}6354, 16\color{red}{23}54, 1625\color{red}{34}, 162\color{red}{45}3, 1\color{red}{56}243,$ cada uno de los cuales tiene exactamente una sucesión.

Como el proceso es reversible, tenemos $S_{n,1} = (n-1)S_{n-1}$ y por lo tanto $S_n = (n-1)S_{n-1} + (n-2)S_{n-2}$ .

---

El $S_{n,k}$ son objeto de la sección 5.4 de la obra de Charalambides Combinatoria Enumerativa . Da la fórmula de la respuesta de Didier (mediante el mismo argumento que utiliza Didier), la que demuestro arriba (manipulando la fórmula de la respuesta de Didier), y las dos siguientes también:

$$nS_n = (n^2-1)S_{n-1} - (-1)^n, \text{ }n \geq 2,$$ $$S_n = D_n + D_{n-1}, \text{ }n \geq 1,$$ donde $D_n$ es el número de derangos en $[n]$ .

También da las siguientes dos expresiones para $S_{n,k}$ : $$S_{n,k} = \frac{(n-1)!}{k!} \sum_{j=0}^{n-k-1} (-1)^j \frac{n-k-j}{j!} = \binom{n-1}{k} S_{n-k},$$ la primera de ellas se obtiene mediante el argumento de inclusión-exclusión aplicado a $S_{n,k}$ en lugar de $S_n$ .