# Counting permutations whose elements are not exactly their index ± 1

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?

• Another commenter suggested searching oeis. Turns out it is listed in there: oeis.org/A078480 and the recursion relation is correct. But I am no closer to understanding how you get that relation. – PPenguin Apr 28 '17 at 20:54
• Good find! The OEIS entry gives a reference; have you checked it out? – Raphael Apr 29 '17 at 8:27
• The OEIS entry even gives you an explicit formula. – Yuval Filmus Apr 29 '17 at 14:29