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.



Permutations which avoid consecutive entries of the form (m,m+1)
This is [A000255](https://oeis.org/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}$$


