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

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.

• The number of permutations of $\{1,\ldots,n+1\}$ with $p(n+1)=n$ is simply the number of permutations of $\{1,\ldots,n\}$; compose any such permutation with the transposition $(n\ n+1)$ yields a bijection between these sets of permutations. – Servaes Dec 15 '18 at 9:42
• But in our case, we count the permutations with $p(i)\neq i$, are you sure there is such bijection? Because when $n+1$ takes $n$'s place, we dont have to worry about $p(n) \neq n$ anymore. – Theorem Dec 15 '18 at 9:46
• Ah, so you mean to count the number of derangements with $p(n+1)\neq n$? I only read your question at a glance, and commented on the last sentence. – Servaes Dec 15 '18 at 9:49
• Yes, I didn't say exactly derangements because that would imply $p(n+1)\neq n+1$, but it is very similar. – Theorem Dec 15 '18 at 9:50
• In a derangement, $n+1$ is as likely to go to $n$ as to any given element of $\{1,\ldots,n\}$. – Lord Shark the Unknown Dec 15 '18 at 10:30

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

These kind of problems (permutations with forbidden positions) can be elegantly solved using rook numbers/polynomials:

Let $$P \subseteq \{1, \ldots, n\}^2$$ be the diagram of forbidden positions. The number of permutations $$p \in S_n$$ such that $$(i,p(i)) \notin P$$ for all $$i = 1, \ldots, n$$ is given by $$\sum_{k=0}^n (-1)^k(n-k)!r_k$$ where $$r_k$$ is the number of ways to place $$k$$ nonattacking rooks on the diagram $$P$$.

In our case the diagram e.g. for $$n=4$$ (the board is then $$5 \times 5$$) is given by:

$$0$$ rooks can be placed in one way on $$P$$. To place $$k$$ rooks on $$P$$, one can place a rook on one of the two positions in the last column of $$P$$ in $$2$$ ways and then place $$k-1$$ rooks on $$n-1$$ remaining positions, or one can just place all $$k$$ rooks in the first $$n-1$$ columns, ignoring the last one. Hence $$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}$$

Therefore the result is \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}

• Is there no simple solutions without pulling any big guns? The problem shouldn't be this complicated and I think I'm missing a key principle. (In addition I'm not sure the solution you achieved is correct) – Theorem Dec 15 '18 at 11:23