Encuentra el número de permutaciones de $1,2,...,6$ con una propiedad especial

Question

Encuentra el número de permutaciones de $1,2,...,6$ con la propiedad de que cada número se asigna a un lugar cuya diferencia con el número original es como máximo $2$ . Es decir, si $f$ es el mapa, entonces para cada $x \in \{1,2,...,6\}$ tenemos $|f(x)-x| \leq 2$ . ¿Alguien tiene una forma elegante de resolver el problema?

Answer 1

Que sea $A(6)$ o en general $A(n)$ .
El número con $n$ en el último lugar es claramente $A(n-1)$ .
Dejemos que $B(n)$ sea el número con $n-1$ en el último lugar.
Dejemos que $C(n)$ sea el número con $n-2$ en el último lugar.
Al considerar dónde $n$ va, obtener recursiones para $A(n)$ , $B(n)$ y $C(n)$ en términos de cada uno.
Como subconjunto de $B(n)$ Si n va en el lugar $n-1$ nos quedamos con $A(n-2)$ . Si los tres últimos son n,n-2,n-1, es $A(n-3)$ . Si los tres últimos son $n,n-3,n-1$ equivale a $B(n-2)$ .
Creo que $C(n)=B(n-1)+A(n-3)+A(n-4)$ .