For $n \ge 3,$ Let $C\_n$ be the cycle graph $(1,2,\cdots n)$ [where $n$ joins back to $1.$] Also let the distance $d(a,b)$ between two nodes $a,b$ be the lesser of $a-b$ mod $n$ and $b-a$ mod $n$. Thus for $n=10$ we have $d(1,10)=1,$ and also for example $d(3,9)=4.$

I'm trying to count the number $f(n)$ of permutations of $\{1,\cdots,n\}$ for which no element is moved more than $1$ unit from where it starts. This means that of course the identity works, as well as the complete cycle $C(n)$ and its inverse. Also one may select any collection of pairwise disjoint "adjacent" 2-cycles, these being $(1,2),(2,3), \cdots (n-1,n),(n,1),$ and together these form an acceptable permutation (viewed as a product of disjoint 2-cycles).

I have fairly carefully looked at the cases $3 \le n \le 9$ and found that for these we have $f(n)=L\_n+2$ where $L\_n$ is the $n$th Lucas number which are those in the list $1,3,4,7,11,\cdots,$ index starting at $1.$ Thus $f(3)=4+2=6,$ not surprising as in this case all nodes are at distance $\le 1$ fom each other. The next is $f(4)=9,$ which one can check on paper. As $n$ increases, it becomes more difficult to keep track of the count.

If someone has access to software which computes the permament of a matrix, then a program could be written to check my conjecture... not much support so far only up to 9. 

I've had no success relating $f(n)$ to its previous 2 values, mainly since I don't see how to relate the counts on cycles whose lengths differ by 1 or 2. Thanks for any insight.