I have been looking at the Menage Problem (https://en.wikipedia.org/wiki/M%C3%A9nage_problem), and am trying to generalize it to count the number of permutations $\sigma \in S_n$ in which for all $i \in \{1,2,3...,n \}$, $\sigma(i) \not \in \{ i - 1, i, i + 1 \}$.
I am working under the assumption that $1$ and $n$ are adjacent (i.e. the points are situated on a circle) and was wondering how I could solve this problem. I have been tried a couple of things (recursion, inclusion-exclusion) but haven't come up with much.
Let $A$ be the $n \times n$ matrix with entries $a_{ij} = 0$ if $i \in \{j-1, j,j+1\}$ and $1$ otherwise. Then your answer is the permanent of $A$.
For more, see OEIS sequence A000183.