How many $n$-permutations have no substrings of the type $(j,j+1)$? How many $n$-permutations have no substrings of the type $(j,j+1)$?
$$1\leq j\leq n-1 \text{    and    } n\geq 2$$
For example, let $n$ be 5:
[3 2 1 5 4] is one of the permutations we have to count.
[4 5 3 1 2] or [1 2 3 5 4] are permutations that we don't have to count.

I reckon this could be a PIE-solvable problem but I really can't figure how to work it out...
 A: If we let $A_j$ be the set of n-permutations which do have the substring $(j,j+1)$ for $1\le j\le n-1$ and let $S$ be the set of all n-permutations,
$\displaystyle\lvert \overline{A}_1\cap\cdots\cap\overline{A}_{n-1}\rvert=\lvert S\rvert-\sum_{i}\lvert A_i\rvert+\sum_{i<j}\lvert A_i\cap A_j\rvert-\sum_{i<j<k}\lvert A_i\cap A_j\cap A_k\rvert+\cdots$
$\hspace{.3 in }\displaystyle=n!-\binom{n-1}{1}(n-1)!+\binom{n-1}{2}(n-2)!-\binom{n-1}{3}(n-3)!+\cdots+(-1)^{n-1}\binom{n-1}{n-1}1!$
$\hspace{.3 in }\displaystyle=(n-1)!\left[n-\frac{n-1}{1!}+\frac{n-2}{2!}-\frac{n-3}{3!}+\cdots+(-1)^{n-1}\frac{1}{(n-1)!}\right]=D_n+D_{n-1}$
A: For the record, a combinatorial approach is possible. Say that a permutation is good if it satisfies the condition in the question. Let $a_n$ be the number of such permutations of $[n]=\{1,\ldots,n\}$.
Each good permutation of $[n]$ can be extended to $n$ different good permutations of $[n+1]$: the $n+1$ can be inserted into the permutation at the beginning, or after any term except $n$. The only good permutations of $[n+1]$ that are not produced in this way are those that have substrings of the form $k,n+1,k+1$ for some $k\le n-1$. Removing the $n+1$ leaves a permutation of $[n]$ that is bad in exactly one place: it contains the substring $k,k+1$, but no other such pair. Removing $k+1$ from the permutation and replacing each $\ell\in\{k+2,\ldots,n\}$ by $\ell-1$ produces a good permutation of $[n-1]$. Conversely, one can start with a good permutation of $[n-1]$, replace any term $k$ by $k,k+1$, and then replace each $\ell\in\{k+1,\ldots,n-1\}$ by $\ell+1$ to get a permutation of $[n]$ that is bad in exactly one place. Thus,
$$a_{n+1}=na_n+(n-1)a_{n-1}\;,$$
and we clearly have the initial conditions $a_1=1=a_2$.
This suggests that we should look at the numbers $na_n$.
$$\begin{array}{rcc}
n:&1&2&3&4&5\\
a_n:&1&1&3&11&53\\
na_n:&1&2&9&44&265
\end{array}$$
The numbers $na_n$ may not be immediately familiar, but it turns out that they are the derangement numbers $D_n$. This empirical observation is easily proved by induction using the recurrence
$$D_{n+1}=n(D_n+D_{n-1})\;.$$
Thus, $na_n=D_n$, and
$$a_n=\frac{D_n}n\;.$$
Any of the formulae for $D_n$ can now be substituted, e.g.,
$$a_n=(n-1)!\sum_{k=0}^n\frac{(-1)^k}{k!}=\frac1n\left\lfloor\frac{n!}e+\frac12\right\rfloor\;,$$
that last being computationally very handy.
