Counting permutations whose elements are not exactly their index ± 1

Question

This is a special case of the question:
Counting permutations whose elements are not exactly their index ± M

The $M=0$ case has already been solved, but no one was sure how to work out the non-zero cases.

So I decided to try to just brute force some values and search the results for a recursion relation. As a test I first tried $M=0$ and searched for recursion relations that looked like: $$ a_n = \sum_{1\le i \le k} (A_i n + B_i) a_{n-i} $$ where $k$ is some cutoff of how far back to search, $A_i \in \{-1,0,1\}$ and $B_i$ some small integers. It was correctly able to find: $$a_n= (n-1)a_{n-1} +(n-1)a_{n-2}$$

So I then tried for $M=1$ and found: $$ a_n= (n) a_{n-1} +(-n+2) a_{n-3} + (-1)a_{n-4} $$

It's possible it's just a coincidence, but I ran a brute force approach to calculating the $M=1$ cases overnight to get a couple more values and it still holds. But even with this potential answer in hand, I cannot figure out a reason this recursion would hold.

Is there a simple combinatoric argument I'm missing here?

Answer 1

Checkout Derangements

"Suppose that there are n people who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as their number."

In applying this to your problem, there would be two hats: the element's index +1, the elements​ index -1.

I'm not certain this solves the problem, but it seems like a step in the right direction.