El número de permutaciones $\langle a_1,\ldots,a_n\rangle$ $\{ 1,\ldots ,n \}$ $a_{i+1} - a_i \ne 1$

Question

Demostrar que para $n>0$, el número de permutaciones $\langle a_1,\ldots,a_n\rangle$ del conjunto de $\{ 1,\ldots ,n \}$ donde $a_{i+1} - a_i \ne 1$ $ i = 1, \ldots, n-1$ es igual a:

$$D_n + (n-1)D_{n-2} +(-1)^{n-1},$$

donde $D_n$ es el número de $n$-permutaciones sin puntos fijos.

He tratado de lidiar con este problema, mediante la inclusión-exclusión de la regla:

$$A_i = (n-1)(n-2)! = (n-1)!$$

y así sucesivamente. Pero para los más grandes de los productos es mucho más complicado. Cualquier sugerencias?

Answer 1

Un poco hacia atrás manera de hacer esto. Tal vez hay un enfoque más directo, pero por ahora vamos a probar esto.

Vamos a hacer uso de dos claves recurrencias de alteraciones, es decir, $$D_n = nD_{n-1} + (-1)^n$$ $$D_n = (n-1)(D_{n-1} + D_{n-2})$$ Permítanme indicar el número de permutaciones como $\alpha_n$. En primer lugar observamos que la ecuación es de hecho igual a $$\alpha_n = D_n + (n-1)D_{n-2} + (-1)^{n-1} = D_n + D_{n-1}$$ Ahora vamos a tratar de generar una periodicidad de $\alpha_n$.

Primero, considere válido permutación en $n$ letras. Si queremos eliminar el elemento$n$, luego tenemos a la izquierda con la validez de una permutación en $n-1$ letras o una permutación con exactamente un "ascenso", es decir, exactamente un $i$ tal que $a_{i+1} - a_i = 1$. Por el contrario, es fácil ver que, dado cualquier válido permutación en $n-1$ letras, no son exactamente $n-1$ posiciones para insertar $n$ a completar una válida permutación en $n$ letras. Podemos insertar $n$ en cualquiera de los huecos salvo que detrás de $n-1$. Asimismo, dado que cualquier permutación con un ascenso de podemos insertar $n$ en exactamente una ubicación para separar el ascenso. Por lo tanto, tenemos la recurrencia $$\alpha_n = (n-1)\alpha_{n-1} + \beta_{n-1}$$ donde $\beta_{n-1}$ es el número de "ascenso" permutaciones en $n-1$ letras.

Ahora buscamos relacionar $\alpha$$\beta$. Dado $n$ letras, en orden a construir una permutación con un ascenso, primero debemos elegir un par de números consecutivos para estar juntos en nuestro permutación. Hay exactamente $n-1$ de estas parejas. Ahora, con respecto a estos números consecutivos como un único elemento, podemos etiquetar como necesario considerar la posibilidad de una permutación en $n-1$ letras. El original de la permutación en $n$ elementos tendrán un ascenso si y sólo si la nueva permutación en $n-1$ elementos no tiene ascensos.

Por ejemplo, considere la posibilidad de una permutación en $\{1,2,3,4,5,6\}$. Primero escogemos un par, decir $(2,3)$. Dicen que nuestro original permutación es $$\pi=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 4 & 6 & 2 & 3 & 1\end{pmatrix}$$ entonces podemos colapso $(2,3)\mapsto 2$ y re-etiquetar $4\mapsto 3$, $5\mapsto 4$, $6 \mapsto 5$, para obtener una permutación en $5$ letras $$\pi' = \begin{pmatrix}1&2&3&4&5\\4&3&5&2&1\end{pmatrix}$$ Usted puede comprobar que este proceso es bijective. Por tanto, tenemos $$\beta_n = (n-1)\alpha_{n-1}$$ que da nuestra recursividad como $$\alpha_n = (n-1)\alpha_{n-1} + (n-2)\alpha_{n-2}$$ con las condiciones iniciales $\alpha_1 = 1$$\alpha_2 = 1$. Es muy fácil de demostrar en este punto que el $\alpha_n = D_n + D_{n-1}$ satisface la anterior recurrencia.