Derangements $p$ de $1,2,\dots,n,n+1$ tal que $n+1$ no va a $n$

Question

Recordemos que el número o Derangements de $1,2,\dots,n$ es una permutación $p$ tal que $p(i) \neq i$ para todos $i$ . Podemos expresarlo con la recurrencia $D_n=(n-1)(D_{n-1}+D_{n-2})$ o mediante la fórmula cerrada $$D_n =\sum_{i=0}^n (-1)^i \frac{n!}{i!}$$

Consideremos ahora el número de permutaciones de $1,2,\dots, n,n+1$ tal que para todo $1\leq i \leq n$ (no $n+1$ ), $p(i)\neq i$ pero también $p(n+1) \neq n$ . Debemos expresar este número mediante $D_n$ s.

Estaba pensando en contar primero el número de permutaciones sin la condición adicional $p(n+1) \neq n$ y recibidos mediante inclusión-exclusión

$$\sum_{r=0}^n (-1)^r \binom{n}{r}(n+1-r)! = \sum_{r=0}^n (-1)^r \frac{n!}{r!}(n+1-r) =$$ $$\sum_{r=0}^n (-1)^r \frac{(n+1)!}{r!}- \sum_{r=1}^n (-1)^r \frac{n!}{(r-1)!}=$$ $$\sum_{r=0}^n (-1)^r \frac{(n+1)!}{r!}- n\sum_{r=0}^{n-1} (-1)^{r+1} \frac{(n-1)!}{r!}=$$ $$=D_{n+1}+nD_{n-1}$$

Ahora tenemos que restarle el número de permutaciones cuando $p(n+1)=n$ que no pude contar.

Gracias de antemano

Answer 1

Este tipo de problemas (permutaciones con posiciones prohibidas) pueden resolverse elegantemente utilizando números de torre/polinomios :

Sea $P \subseteq \{1, \ldots, n\}^2$ sea el diagrama de posiciones prohibidas. El número de permutaciones $p \in S_n$ tal que $(i,p(i)) \notin P$ para todos $i = 1, \ldots, n$ i $$\sum_{k=0}^n (-1)^k(n-k)!r_k$$ donde $r_k$ es el número de maneras de colocar $k$ torres no atacantes en el diagrama $P$ .

En nuestro caso, el diagrama, por ejemplo para $n=4$ (el tablero se $5 \times 5$ ) viene dada por:

$0$ las torres pueden colocarse de una manera en $P$ . Para colocar $k$ torres en $P$ se puede colocar una torre en una de las dos posiciones de la última columna de $P$ en $2$ formas y, a continuación, coloque $k-1$ torres en $n-1$ posiciones restantes, o se pueden colocar todas $k$ torres en la primera $n-1$ columnas, ignorando la última. Por lo tanto $$r_k = \begin{cases} 1, \text{ if }k=0\\ 2{n-1 \choose k-1} + {n-1 \choose k}, \text{ if }k \ge 1 \end{cases} = \begin{cases} 1, \text{ if }k=0\\ {n \choose k} + {n-1 \choose k-1}, \text{ if }k \ge 1 \end{cases}$$

Por lo tanto, el resultado es \begin{align} \sum_{k=0}^n (-1)^k(n-k)!r_k &= \sum_{k=0}^n (-1)^k(n-k)!{n \choose k} + n! + \sum_{k=1}^n (-1)^k(n-k)!{n-1 \choose k-1} \\ &= D_n + n! - \sum_{j=0}^{n-1} (-1)^j((n-1)-j)!{n-1 \choose j} \\ &= D_n + n! - D_{n-1} \end{align}

Answer 2

Llamar a una permutación $\sigma$ de $\{1,\ldots,n+1\}$ bien si $\sigma(i)\neq i$ para todos $1\leq i\leq n$ y y $\sigma(n+1)\neq n$ .

Sea $\sigma$ sea una buena permutación, y sea $a:=\sigma(n+1)$ y $b:=\sigma^{-1}(n+1)$ de modo que $a\neq n$ . Si $a\neq b$ entonces la permutación $(a\ n+1)\sigma$ fija $n+1$ y es un trastorno de $\{1,\ldots,n\}$ . Si $a=b$ entonces $(a\ n+1)\sigma$ fija $a$ y $n+1$ y es un trastorno de $\{1,\ldots,n\}\setminus\{a\}$ .

A la inversa, para cualquier trastorno $\sigma$ de $\{1,\ldots,n\}$ y cualquier $a\in\{1,\ldots,n+1\}$ con $a\neq n$ la composición $(a\ n+1)\sigma$ es bueno. Además, para cualquier $a\in\{1,\ldots,n-1\}$ y cualquier trastorno $\sigma$ de $\{1,\ldots,n\}\setminus\{a\}$ la composición $(a\ n+1)\sigma$ es bueno.

Esto demuestra que el número de permutaciones buenas es $nD_n+(n-1)D_{n-1}$ donde $D_m$ denota el número de desviaciones de $\{1,\ldots,m\}$ .