A recurrence relation isn’t too hard. Consider an acceptable permutation $\pi$ of $[n+1]$. If you remove the $n+1$, there are two general possibilities for the resulting permutation of $[n]$.
- It may be acceptable.
- It may be unacceptable, but only because the number that was immediately to the left of $n+1$ in $\pi$ is one less than the number that was immediately to the right of $n+1$ in $\pi$.
There are $f(n)$ acceptable permutations of $[n]$, and $n+1$ can be inserted into any of them in any of the $n$ slots that are not immediately to the right of the $n$, so these account for $nf(n)$ acceptable permutations of $[n+1]$. It only remains to count the permutations of $[n]$ that are unacceptable in exactly one position.
Suppose that $\sigma$ is such a permutation, and in it $k$ and $k+1$ are adjacent in that order. Remove $k+1$ and decrease every remaining element of $\sigma$ that is greater than $k$ by $1$; the result is an acceptable permutation of $[n-1]$. Conversely, if you start with an acceptable permutation of $[n-1]$, pick any $k$ in it, increase by $1$ every element that is greater than $k$, and insert $k+1$ immediately to the right of $k$, you get a permutation of $[n]$ that is unacceptable in exactly one position. There are $n-1$ choices for $k$, so there are $(n-1)f(n-1)$ permutations of $[n]$ that are unacceptable in exactly one position.
Putting the pieces together, we see that $f(n+1)=nf(n)+(n-1)f(n-1)$. (This differs from the recurrence given for OEIS A000255, mentioned in the comments, because the indexing is off by $1$.)
