A special case of double derangement with $ k-1 \ne\sigma(k) \ne k $

241 Views Asked by At

How many permutations on a set $[n]$ does there exist such that :

$$\forall k \in [n]:\sigma(k) \ne k \;\;\;\text{and}\;\;\;\forall k \in [n]\setminus\left\{1\right\}: \sigma (k) \ne k-1\;\;\;\text{and}\;\;\;\sigma (1) \ne n$$


Indeed we are looking for the derangement such that there does not exist any elements mapped to the element before itself (with the assumption that $\sigma (1) \ne n$).

Define: $$\overline A_{}:=\left\{\sigma \in S_{n}:\forall k \in [n]:\sigma(k) \ne k\right\}$$ $$\overline B_{}:=\left\{\sigma \in S_{n}:\forall k \in [n]\setminus\left\{1\right\}:\sigma(k) \ne k-1 \;\;\;\text{and}\;\;\;\sigma (1) \ne n \right\}$$

What we want can be derived using inclusion-exclusion :

$$n!-\ \left| A_{} \cup B\right|$$ $$=n!-\left| A_{} \right|-\left| B_{} \right|+\left| A \cap B_{} \right|$$ $$=n!-\bigcup_{k=1}^{n}\left|A_k\right|-\bigcup_{k=1}^{n}\left|B_k\right|+\bigcup_{k=1}^{n}\left|A_k\right| \cap \bigcup_{k=1}^{n}\left|B_k\right|$$

Where $A_k,B_k$ is the set of permutations with their $k$th term fixed.

From the number of derangement we conclude that :

$$\bigcup_{k=1}^{n}\left|A_k\right|=n!\sum_{i=1}^{n}\frac{\left(-1\right)^{i+1}}{i!}=\bigcup_{k=1}^{n}\left|B_k\right|$$

However for $\bigcup_{k=1}^{n}\left|A_k\right| \cap \bigcup_{k=1}^{n}\left|B_k\right|$ I could not find any closed form,even I could not finish the computation,besides I'm not sure if I've done the other part correctly.


Note:

  • What the question wants is a special case of a double derangement with two permutations $\text{id}(k),\pi(k) \in S_n$ such that $\text{id}(k)=k$ and $\pi(k)=k-1$.

  • The other cases has been discussed earlier:

The number of derangements on $[n]$ such that $\sigma(n) \ne n-1$ is:

$$\frac{\left(n-2\right)D_{n}}{n-1}$$

The number of derangements on $[n]$ such that $\sigma(n) \ne n-1$ and $\sigma(n-1) \ne n-2$ is:

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

The number of derangements on $[n]$ such that $\sigma(n) \ne n-1$ and $\sigma(n-1) \ne n-2$ and $\sigma(n-2) \ne n-3$ is:

$$\frac{\left(n-4\right)D_{n}}{n-1}+\frac{3D_{n-1}}{n-2}$$

Added: The question is exactly Professor Tait's Problem of Arrangement,but I Want to know does there exist any way to continue from my way? besides are the three partial cases helpful to derive a formula for the main problem?