How many derangements on a set $[n]$ does there exist such that $\sigma(n)\ne n-1$ ,$\sigma(n-1)\ne n-2$,$\sigma(n-2)\ne n-3$

Question

How many derangements on a set $[n]$ does there exist such that $\sigma(n)\ne n-1$ ,$\sigma(n-1)\ne n-2$,$\sigma(n-2)\ne n-3$

Define : $$ \zeta_{n}=\left\{\sigma \in S_n:\forall k \in [n]:\sigma(k) \ne k , \sigma(n)=n-1\right\}$$

$$ \zeta_{n-1}=\left\{\sigma \in S_n:\forall k \in [n]:\sigma(k) \ne k ,\sigma(n-1)=n-2\right\}$$

$$ \zeta_{n-2}=\left\{\sigma \in S_n:\forall k \in [n]:\sigma(k) \ne k ,\sigma(n-2)=n-3\right\}$$

Then we want : $$!n-\left( \bigcup_{i=0}^{2}\zeta_{n-i}\right)$$ Which is equivalent to :

$$!n-\zeta_{n}-\zeta_{n-1}-\zeta_{n-2}+\zeta_{n}\cap \zeta_{n-1}+\zeta_{n}\cap \zeta_{n-2}+\zeta_{n-1}\cap \zeta_{n-2}-\zeta_{n}\cap \zeta_{n-1} \cap \zeta_{n-2}$$

The size of the sets $\zeta_{n},\zeta_{n-1},\zeta_{n-2}$ are the same and is equal to $\frac{D_n}{n-1}$.

For $\zeta_{n}\cap \zeta_{n-1}$ there are two cases,depending on whether $\sigma(n-2)=n$ or not we have $D_{n-3}+D_{n-2}$ selections.

For $\zeta_{n-1}\cap \zeta_{n-2}$ there are two cases,depending on whether $\sigma(n-3)=n-1$ or not we have$D_{n-3}+D_{n-2}$ selections.

For $\zeta_{n}\cap \zeta_{n-2}$ there are eight cases:

Either $\sigma(n-1)=n,\sigma(n-3)=n-2$ or $\sigma(n-1)=n,\sigma(n-3)\ne n-2$ or $\sigma(n-1) \ne n,\sigma(n-3)=n-2$ or $\sigma(n-1) \ne n,\sigma(n-3)\ne n-2$. The other cases are the same but we explore the permutations on $\sigma(n-1)=n-2,\sigma(n-3)=n$,gathering all of them gives $2\left(D_{n-4}+2D_{n-3}+D_{n-2}\right)$ cases.

Now consider $\zeta_{n}\cap \zeta_{n-1} \cap \zeta_{n-2}$,depending on whether $\sigma(n-3)=n$ or not we have $D_{n-4}+D_{n-3}$ selections.

So summing the cases gives the answer:$$D_n-3\frac{D_n}{n-1}+D_{n-3}+D_{n-2}+2\left(D_{n-4}+2D_{n-3}+D_{n-2}\right)+D_{n-3}+D_{n-2}-D_{n-4}-D_{n-3}$$ Which is equivalent to:

$$D_n-3\frac{D_n}{n-1}+5D_{n-3}+4D_{n-2}+D_{n-4}$$ I'm not sure if the answer is right,so can someone check that?(I have not tried to rewrite the last expression in its simplest form).

Answer 1

Here is a presentation which is both simpler and more systematic than your original attempt.

In what follows, $\Delta(X)$ denotes the set of all derangements on $X$ for any set $X$, and we also write $\Delta_n$ for $\Delta_{[n]}$ where $[n]=1,2,\ldots,n$. For $\sigma \in \Delta(X)$ and $x\in X$, let $S_x(\sigma)$ be the permutation on $X\setminus \lbrace x \rbrace$ which coincides with $\sigma$ everywhere except on $\sigma^{-1}(x)$, where it equals $\sigma(x)$. For $Z\subseteq \Delta (X)$, let $p_x(Z)=\lbrace \sigma \in Z | S_x(\sigma) \in \Delta(X\setminus \lbrace x \rbrace)\rbrace$, and $q_x(Z)=Z\setminus p_x(Z)=\lbrace \sigma \in Z |\sigma(\sigma(x))=x\rbrace$. We call the partition $Z=p_x(Z)\cup q_x(Z)$ the $x$-decomposition of $Z$.

Let us count the elements in $A=\zeta_n \cap \zeta_{n-1}$. We apply $n-1$-decomposition. We see that $q_{n-1}(A)$ is empty, so $|A|=|p_{n-1}(A)|$, but $p_{n-1}(A)$ is in bijection with $\lbrace \tau \in \Delta([n]\setminus \lbrace n-1 \rbrace) | \tau(n)=n-1 \rbrace$, so $|p_{n-1}(A)|=\frac{D_{n-1}}{n-2}$.

Replacing $n$ with $n-1$, we see that $B=\zeta_{n-1} \cap \zeta_{n-2}$ has the same cardinality, $\frac{D_{n-1}}{n-2}$.

Let us count the elements in $C=\zeta_n \cap \zeta_{n-2}$. We start by applying $n$-decomposition. Since $p_{n}(C)=\lbrace \tau \in \Delta([n-1]) | \tau(n-2)=n-3 \rbrace$, we have $|p_n(C)|=\frac{D_{n-1}}{n-2}$. So we need now to count the elements in $q_n(C)=\lbrace \sigma \in \Delta_n | \sigma(n)=n-1,\sigma(n-1)=n, \sigma(n-2)=n-3 \rbrace$, which is obviously in bijection with $\sigma \in \Delta_{n-2} | \sigma(n-2)=n-3 \rbrace$, so $|q_n(C)|=\frac{D_{n-2}}{n-3}$. Finally $|C|=\frac{D_{n-1}}{n-2}+\frac{D_{n-2}}{n-3}$.

Let us count the elements in $E=\zeta_n \cap \zeta_{n-1} \cap \zeta_{n-2}$. We start by applying $n-2$-decomposition. We see that $q_{n-2}(E)$ is empty, so $|E|=|p_{n-2}(E)|$. We now need to count the elements in $F=p_{n-2}(E)$ where $F=\lbrace \sigma \in \Delta([n]\setminus \lbrace n-2 \rbrace) | \sigma(n)=n-1,\sigma(n-1)=n-3 \rbrace$. By applying $n-1$-decomposition to $F$, we see that $F$ is in bijection with $\lbrace \sigma \in \Delta([n]\setminus \lbrace n-2,n-1 \rbrace) | \sigma(n)=n-3 \rbrace$. Thus $|E|=\frac{D_{n-2}}{n-3}$.

Finally, the answer to your question is

$$ \begin{array}{lcl} N &=& D_n-(|\zeta_n|+|\zeta_{n-1}|+|\zeta_{n-2}|-|A|-|B|-|C|+|E|) \\ &=& D_n-3\frac{D_n}{n-1}+\frac{3D_{n-1}}{n-2}+\frac{D_{n-2}}{n-3}-\frac{D_{n-2}}{n-3} \\ &=& \frac{(n-4)D_n}{n-1}+\frac{3D_{n-1}}{n-2}+\frac{D_{n-2}}{n-3}-\frac{D_{n-2}}{n-3} \\ &=& \frac{(n-4)D_n}{n-1}+\frac{3D_{n-1}}{n-2} \\ \end{array} $$