Number of permutations of six numbers with certain restrictions There are $6!$ permutations of the numbers $1...6$, like $156234$.
in this permutation, $1$ is in the first location, $5$ is in the second, etc.
The problem is: how many permutations with the numbers $1...6$ are there that follow this rule: each number is either in the location that is equal to its value, or in a location that differs from its value by $1$ ($+1$ or $-1$), or in a location that differs from its value by $2$ ($+2$ or $-2$).
For example: the permutation $245163$ doesn't follow the rule only because $1$ is in the 4th place, and because $3$ is in the 6th place.
I solved a weaker version of this problem, in which there are only $4$ numbers with the same rule, by taking the overall number of permutations with the $4$ numbers, subtracting those who had $4$ in the first place and those who had $1$ in their 4th place, and adding those who had $4$ in their first place and $1$ in their 4th place, to avoid subtracting them twice: $4!-3!-3!+2 = 
14$.
This strategy worked, but once you get to just $5$ numbers, there are just too many cases to add and subtract...
 A: Counting the resulting numbers using brute force you get the sequence
$$(b_n)_{n\geq2}=(2, 6, 14, 31, 73, 172, 400,\ldots)\ .$$
This is sequence A002524 at OEIS, where one may find further information.
A recursion for these numbers can be obtained as follows: Imagine that we have an infinite row of seats numbered $1$, $2$, $3$, $\ldots$, and infinitely many people holding numbered tickets for these seats. We now let the people take seats in the order of their ticket numbers, whereby nobody may take a seat more than two away from his number. When $n$ people have been seated the seats with numbers $\geq n+3$ are still free. On the other hand the seats with numbers $\leq n-2$ must have been  taken, or it will be impossible to complete the task. For the seats $n-1$, $n$, $n+1$, $n+2$ we have one of the following six patterns, whereby a bullet denotes a taken seat:
$$\eqalign{&p_1: \ \bullet\bullet\circ\circ,\qquad p_2: \ \bullet\circ\bullet\circ,\qquad p_3: \ \bullet\circ\circ\bullet,\cr &p_4: \ \circ\bullet\bullet\circ,\qquad p_5: \ \circ\bullet\circ\bullet,\qquad p_6: \ \circ\circ\bullet\bullet\ .\cr}\tag{1}$$
Denote by $a_k(n)$ the number of legal seatings so far that end in pattern $p_k$. Now the person with ticket $n+1$ has to take a seat. If the present pattern is one of $p_4$, $p_5$, or $p_6$ this person is obliged to take seat $n-1$. Otherwise the person has three choices: One of the two empty seats in $(1)$, or seat $n+3$. After the choice is made, again one of the six patterns results, but shifted one unit to the right.
It follows that we have a linear recursion scheme
$$a_i(n+1)=\sum_{k=1}^6 c_{ik}\, a_k(n)\qquad(1\leq i\leq 6)$$
with a constant $6\times6$-matrix $C=\bigl[c_{ik}\bigr]$ that has to be determined once and for all by chasing the cases. The resulting matrix is
$$C=\left[\matrix{1&1&0&1&0&0\cr
1&0&1&0&1&0\cr
1&0&0&0&0&0\cr
0&1&1&0&0&1\cr
0&1&0&0&0&0\cr
0&0&1&0&0&0\cr}\right]\ .$$ Finally one has  to determine the initial values $a_k(2)$ by hand. One finds ${\bf a}(2)=(2,2,1,2,1,1)$, and then $${\bf a}(n)=C^{n-2}{\bf a}(2)\ .\tag{2}$$
Given all this, the numbers you are interested in are the numbers $b_n:=a_1(n)$ $(n\geq2)\>$. It turns out that these numbers satisfy the recursion
$$b_n=b_{n-1}+2b_{n-2}+2b_{n-3}+2b_{n-4}-b_{n-5}-b_{n-6}\qquad(n\geq8)\ .\tag{3}$$
In order to make use of $(3)$ you have to determine the $b_n$ $(2\leq n\leq7)$ the hard way, or using $(2)$.
