Permutations which avoid consecutive entries of the form (m,m+1)

Question

I found an interesting question on quora and need help in solving this question. I've just started understanding permutations but could not understand as to how I can come up with a general formula for this problem. Consider all permutations of the numbers 1 to n. A good permutation is one where for any number i at position p in the permutation, i+1 is never at position p+1. For a given n, count the number of good permutations.

For example, for n = 3, the good permutations are:

1, 3, 2

2, 1, 3

3, 2, 1

Come up with a form of an answer which can be easily calculated.

Answer 1

This is A000255, and can be described in several ways. Perhaps the easiest to see is the recursion $$a(n+1)=na(n)+(n-1)a(n-1)$$ Note that my indexing is different from the OEIS, in my notation $a(n)$ counts the good permutations of $[n]$. To see the recursive identity justify that a good permutation of $[n+1]$ can be obtained either by picking a good permutation of $[n]$ and then inserting $n+1$ at a random place (as long as it's not right after $n$), or by picking a permutation of $[n]$ with exactly one occurrence of the pattern $(m,m+1)$ and placing $n+1$ in the middle of $i$ and $i+1$. I'll leave out the details.

This leads to an explicit formula for $a(n)$ as $\frac{D_{n+1}}{n}$, where $D_n$ are the derangement numbers. An exponential generating function can also be written: $$\sum_{n=0}^{\infty} a(n)\frac{x^n}{n!}=\frac{1}{e^x(1-x)^2}$$