Permutation count in cycle graphs 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.
 A: Consider your $n$ transpositions. Label them by the least element, so you get the set $\{1,...,n\}$. How many subsets are there with no adjacent numbers? Call this $A_n$.
Such a set either contains $n$ or it doesn't. There are clearly $A_{n-1}$ of the second kind. Elements of the first kind may not contain $n-1$ nor $1$, so there are $A_{n-2}$ of them.
Therefore, $A_n=A_{n-1}+A_{n-2}$.
Plus, you have the full cycle and its inverse, so the number you want is $A_n+2$.
A: Just like the Fibonacci numbers give the number of ways to tile an $n\times 1$ grid of squares with square and domino tiles, the Lucas numbers count the number of ways to tile an annulus divided into $n$ equal sections with rounded "square" and "domino" tiles. This tiling question is equivalent to your problem. 
To prove this, condition on the "last" tile in the circle. Numbering the sectors clockwise from $1$ to $n$, the "first" tile is the one covering sector $1$, while the "last" tile is anti-clockwise adjacent to the first. Deleting the last tile, and contracting the circle to fill the gap, you get a tiling of either an $n-1$ or $n-2$ sector annulus. If the last tile does not cover square $n$, then you will have to renumber sector $n$ after the deletion, so the sectors are still numbered $1$ to $k$, where $k=n-1$ or $n-2$. A little thought shows this is a bijection from $n$-tilings to the disjoint union of $(n-1)$-tilings and $(n-2)$-tilings when $n\ge 3$, proving 
$$
f(n)=f(n-1)+f(n-2)\tag{$n\ge 3$}
$$
Combined with the base cases $f(1)=1$, $f(2)=3$, this shows $f$ agrees with a shift of the Lucas numbers.
