Number of permutation such that $\sigma (k) \ne k-1$

Question

How many permutations on a set $[n]$ does there exist such that $$\forall k \in [n]\setminus\left\{1\right\}: \sigma (k) \ne k-1\;\;\;\text{and}\;\;\;\sigma (1) \ne n$$

Where $\sigma (k) \in S_n$.

---

The question is similar to the derangement problem,and in my opinion the number of such permutations is the same as the number of the derangements on a set,plus if we denote the number of such permutations with $w_n$ on a set $[n]$,then I think it's true and reasonable to write an equivalent for $n!$ such that:

$$n!=\sum_{k=0}^{n}\binom{n}{k}w_{n-k}$$

However I think $w_n=D_n$,but I'm not sure how to find a recurrence relation for $w_n$,I tried the similar argument used for proving $D_n=\left(n-1\right)\left(D_{n-1}+D_{n-2}\right)$,but it seems to be more difficult.

---

Notice that I used a similar argument ,and not the same argument,since I think the same cannot be used to derive a recurrence relation for $w_k$,I want to know how to find a recurrence for $w_k$ using the similar method used to derive $D_n=\left(n-1\right)\left(D_{n-1}+D_{n-2}\right)$.

Answer 1

Your considerations are correct for me. I suggest a way to conclude the computation of $w_n$ thanks to what we know for $D_n$ and what you wrote.

Denote with $X_n = \{\sigma\in S_n \ | \ \sigma(k)\neq k-1 \pmod{n}\}$ the set you are looking for and $Y_n=\{\sigma\in S_n \ | \ \sigma(k)\neq k \}$ the set of the Derangement problem. Hence $|X_n|=w_n$ and $|Y_n|=D_n$.

Consider the maps \begin{gather} X_n\longrightarrow Y_n, \qquad \sigma\longmapsto (1,2,3,4,...,n)\circ \sigma\\ Y_n\longrightarrow X_n, \qquad \rho\longmapsto (1,2,3,4,...,n)^{-1}\circ \rho \end{gather} Since they are one the inverse of the other, this is a bijection between the two sets and $w_n=D_n$.

Answer 2

It actually is the derangement problem in disguise: in each problem there is exactly one forbidden target for each element of $[n]$, and each element of $[n]$ is a forbidden target for exactly one element of $[n]$. Let $\pi$ be the following permutation of $[n]$:

$$\pi:[n]\to[n]:k\mapsto\begin{cases} 1,&\text{if }k=n\\ k+1,&\text{otherwise.} \end{cases}$$

A permutation $\sigma$ of $[n]$ satisfies your condition if and only if $\pi\circ\sigma$ is a derangement of $[n]$. If $\Pi_n$ is the set of permutations of $[n]$, the map $\sigma\mapsto\pi\circ\sigma$ is clearly a bijection from $\Pi_n$ to itself, so $w_n=D_n$. Clearly the same is true for any $\pi\in\Pi_n$: each yields another variant of the derangement problem.

Once you have this, you know that the numbers $w_n$ satisfy the same recurrences as the derangement numbers, and there’s no real need to find a separate proof. One can prove directly that $w_n=(n-1)(w_{n-1}+w_{n-2})$ using an argument with the same basic structure as the usual combinatorial argument for the corresponding derangement recurrence, but the proof uses a somewhat more complicated version of the idea that I used above and is harder than simply exhibiting a bijection with the set of derangements.

Added: And here is such an argument. It’s quite possible that this could be simplified or cleaned up a bit: I did it fairly hurriedly.

Say that a permutation $\sigma$ of $[n]$ is good if $\sigma(k)\ne k-1$ for $k\in[n]\setminus\{1\}$, and $\sigma(1)\ne n$. Suppose that $\sigma$ is a good permutation of $[n]$. There are $n-1$ possible choices for $\sigma(n)$; suppose that $\sigma(n)=k\ne n-1$. There are now two possibilities. In what follows replace $k+1$ by $1$ if $k=n$.

Suppose first that $\sigma(k+1)\ne n-1$. Then $\sigma$ must map $[n-1]$ bijectively to $[n]\setminus\{k\}$ subject to certain restrictions. If $k=n$, $\sigma\upharpoonright[n-1]$ is simply a good permutation of $[n-1]$, and any good permutation of $[n-1]$ can be extended to a good permutation of $[n]$ that takes $n$ to $n$, so there are $w_{n-1}$ possibilities for $\sigma\upharpoonright[n-1]$. If $k\ne n$, the restrictions are as follows: $\sigma(\ell)\ne\ell-1$ for $\ell\in[n]\setminus\{1,k+1\}$, $\sigma(1)\ne n$, and $\sigma(k+1)\ne n-1$. Let

$$\varphi:[n]\setminus\{k\}\to[n-1]:\ell\mapsto\begin{cases} k,&\text{if }\ell=n-1\\ n-1,&\text{if }\ell=n\\ \ell,&\text{otherwise;} \end{cases}$$

then $\sigma\upharpoonright[n-1]$ satisfies those restrictions iff $\hat\sigma=\varphi\circ(\sigma\upharpoonright[n-1])$ is a good permutation of $[n-1]$. (E.g., $\sigma(k+1)=n-1$ iff $\hat\sigma(k+1)=\varphi(n-1)=k$.) Once again there are $w_{n-1}$ possible choices for $\sigma\upharpoonright[n-1]$, so there are altogether $(n-1)w_{n-1}$ good permutations $\sigma$ of $[n]$ such that $\sigma(k+1)\ne n-1$.

Now suppose that $\sigma(k+1)=n-1$. Then $\sigma$ must map $[n-1]\setminus\{k+1\}$ bijectively to $[n]\setminus\{k,n-1\}$, again subject to certain restrictions. If $k=n$, $\sigma$ maps $[n-1]\setminus\{1\}$ bijectively to $[n-2]$ in such a way that $\sigma(\ell)\ne\ell-1$ for $\ell\in[n-1]\setminus\{1\}$. Let

$$\varphi:[n-2]\to[n-1]\setminus\{1\}:\ell\mapsto\begin{cases} n-1,&\text{if }\ell=1\\ \ell,&\text{otherwise;} \end{cases}$$

then $\sigma\upharpoonright[n-1]\setminus\{1\}$ satisfies those restrictions iff $\hat\sigma=\sigma\circ\varphi$ is a good permutation of $[n-2]$. (E.g., $\hat\sigma(1)=n-2$ iff $\sigma(n-1)=n-2$.)

If $k\ne n$, the restrictions are that $\sigma(\ell)\ne\ell-1$ for $\ell\in[n-1]\setminus\{1,k+1\}$, and $\sigma(1)\ne n$. Let

$$\varphi:[n-2]\to[n-1]\setminus\{k+1\}:\ell\mapsto\begin{cases} \ell,&\text{if }1\le\ell\le k\\ \ell+1,&\text{if }k+1\le\ell\le n-2 \end{cases}$$

and

$$\psi:[n]\setminus\{k,n-1\}\to[n-2]:\ell\mapsto\begin{cases} \ell,&\text{if }1\le\ell<k\\ \ell-1,&\text{if }k<\ell<n-1\\ n-2,&\text{if }\ell=n\;, \end{cases}$$

and let $\hat\sigma=\psi\circ\sigma\circ\varphi$; then $\sigma$ satisfies those restrictions iff $\hat\sigma$ is a good permutation of $[n-2]$. (E.g., $\hat\sigma(1)=n-2$ iff $\sigma(\varphi(1))=n$ iff $\sigma(1)=n$.) Thus, whenever $\sigma(k+1)=n-1$ there are $w_{n-2}$ ways to choose the rest of $\sigma$, so there are $(n-1)w_{n-2}$ good permutations of $[n]$ such that $\sigma(k+1)=n-1$.

Altogether, then, we have $w_n=(n-1)(w_{n-1}+w_{n-2})$.

Answer 3

I could find another proof:

---

Divide the cases into two parts:

• $\sigma(n)=k$ where $1\le k\le n-2$$\tag{I}$
• $\sigma(n)=n$$\tag{II}$

$\color{red}{\text{(I)}}$ If $\sigma(n)=k$, then either $\sigma(k+1)=n-1$ or $\sigma(k+1) \ne n-1$,which generates $w_{n-2}$ and $w_{n-1}$ cases,also there are $n-2$ such $k$,and so $\left(n-2\right)\left(w_{n-1}+w_{n-2}\right)$.

$\color{red}{\text{(II)}}$ If $\sigma(n)=n$,then there are $n-1$ places for which $1$ can be mapped to,indeed we are looking for the number of permutations on a set $[n-1]$ such that $$\forall k( 2\le k\le n-1:\sigma(k) \ne k-1)$$Using inclusion-exclusion principle (refer to this link) we see that the number of such permutations is :

$$\left(n-2\right)w_{n-3}+\left(n-1\right)w_{n-2}$$ Summing these two cases implies:

$$\left(n-2\right)\left(w_{n-1}+ w_{n-2}\right)+\left(n-2\right)w_{n-3}+\left(n-1\right)w_{n-2}$$

$$=\left(n-2\right)\left(w_{n-1}+w_{n-2}+w_{n-3}\right)+\left(n-1\right)w_{n-2}$$

$$=\left(n-2\right)\left(w_{n-1}+\frac{w_{n-1}}{n-2}\right)+\left(n-1\right)w_{n-2}$$

$$=\left(n-1\right)\left(w_{n-1}+w_{n-2}\right)\;\;\blacksquare$$