Cfrgtkky

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 $1leq 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!}- nsum_{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

Call a permutation $sigma$ of ${1,ldots,n+1}$ good if $sigma(i)neq i$ for all $1leq ileq 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 $aneq n$. If $aneq 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 $ain{1,ldots,n+1}$ with $aneq n$ the composition $(a n+1)sigma$ is good. Also, for any $ain{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}