Derangements $p$ of $1,2,\dots,n,n+1$ such that $n+1$ doesn’t go to $n$

combinatoricsinclusion-exclusionpermutations

Recall that the number or Derangements of $1,2,\dots,n$ is a permutation $p$ such that $p(i) \neq i$ for all $i$. We can express it with the recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$ or by the closed formula $$D_n =\sum_{i=0}^n (-1)^i \frac{n!}{i!}$$

Now we consider the number of permutations of $1,2,\dots, n,n+1$ such that for all $1\leq i \leq n$ (not $n+1$), $p(i)\neq i$, but also $p(n+1) \neq n$. We need to express this number using $D_n$s.

I was thinking of first counting the number of permutations without the additional condition $p(n+1) \neq n$ and received using inclusion-exclusion

$$\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}$$

Now we need to subtract from this the number of permutations when $p(n+1)=n$, which I wasn't able to count.

Thanks in advance

Best Answer

Call a permutation $\sigma$ of $\{1,\ldots,n+1\}$ good if $\sigma(i)\neq i$ for all $1\leq i\leq n$ and and $\sigma(n+1)\neq n$.

Let $\sigma$ be a good permutation, and let $a:=\sigma(n+1)$ and $b:=\sigma^{-1}(n+1)$, so that $a\neq n$. If $a\neq b$ then the permutation $(a\ n+1)\sigma$ fixes $n+1$ and is a derangement of $\{1,\ldots,n\}$. If $a=b$ then $(a\ n+1)\sigma$ fixes $a$ and $n+1$, and is a derangement of $\{1,\ldots,n\}\setminus\{a\}$.

Conversely, for any derangement $\sigma$ of $\{1,\ldots,n\}$ and any $a\in\{1,\ldots,n+1\}$ with $a\neq n$ the composition $(a\ n+1)\sigma$ is good. Also, for any $a\in\{1,\ldots,n-1\}$ and any derangement $\sigma$ of $\{1,\ldots,n\}\setminus\{a\}$ the composition $(a\ n+1)\sigma$ is good.

This shows that the number of good permutations is $nD_n+(n-1)D_{n-1}$, where $D_m$ denotes the number of derangements of $\{1,\ldots,m\}$.