Arranging $n$ different numbers on a circle such that difference of two adjacent ones is at most two

Question

In how many ways can the numbers $1, \ldots, n$ be arranged in a circle so that adjacent numbers always differ by $1$ or $2$?

There are just two possibilities for every $n$, right?

Answer 1

Fix the location of $1$. Then its neighbors must be $2,3$ in one order of the other. Fix that order. Then I claim that the rest of the numbers are locked in. It is easy to see that that the string that starts $1,2$ must continue with $4$ while the string that starts $1,3$ must continue with $5$. Let's show that this pattern continues. We remark that the obvious extension of this works...that is $1,2,4,6,\cdots$ in one direction, $1,3,5,7,\cdots$ in the other, meeting at $n,n-1$ is one order or the other. We must show that these are the only two cases.

Indeed, the numbers must go by $2's$ from the start...the two clockwise and counterclockwise strings meet at $n,n-1$ in one order or the other. We can see this inductively. Suppose we have shown it up to $k-1<n$. Then the strings are $1,2,4,\cdots$ and $1,3,5,\cdots$. Depending on the parity of $k$ one of these ends in $k-2$ and the other ends in $k-1$. What can go in the free spot next to $k-2$? Well, the numbers less than or equal to $k-1$ are already in place, so it has to be $k$, and we are done.

Answer 2

One solution is obtained by taking first the odd numbers between $1$ and $n$ in increasing order, and then the even numbers between $1$ and $n$ in decreasing order. For instance, for $n=9$, this gives $1,3,5,7,9,8,6,4,2$.

Then one can show that this is the only solution, up to the symmetries of the $n$-gon, i.e. the group of symmetries generated by the cyclic permutation (in the example, applying it gives $3,5,7,9,8,6,4,2,1$) and the reflection (on the example, it gives $2,4,8,9,7,5,3,1$).

The proof goes as follows. Using rotations, I can put $1$ in the first position. Because of the rules, its neighbours are $2$ and $3$. Using the reflection freedom, I can put $3$ on the right of $1$. Then the only possible neighbour of $2$ that remains is $4$. And the only possible neighbour of $3$ is $5$. One proceeds by induction to show the unicity of the solution.