How many permutations of $\{1, \ldots, n\}$ exist such that none of them contain $(i, i+1)$ (as a sequence) for $i \in {1,...,(n-1)}$? How many permutations of $\{1, \ldots, n\}$ exist such that none of them contain $(i, i+1)$ (as a sequence of two consecutive entries) for $i \in \left\{1,...,(n-1)\right\}$?
First thing that comes to my mind is to find all that have $(i, i+1)$, then subtract that from all permutations. But then we can have $(i, i+1, i+2)$ which we subtracted twice, once in $(i, i+1)$ and once in $(i+1, i+2)$. And so on for $3$ and more. How do I calculate this?
 A: If we take such a permutation on $\{1,\ldots,n\}$ and delete $n$ we obtain either:


*

*a permutation of $\{1,\ldots,n-1\}$ without any $(i,i+1)$ subsequence, or

*a permutation of $\{1,\ldots,n-1\}$ with exactly one $(i,i+1)$ subsequence, which occurs when the original sequence had a $(i,n,i+1)$ subsequence.
In this case, if we instead delete the $n$ and $i+1$ from this sequence and relabel elements $e \geq i+2$ with $e-1$, we obtain a a permutation of $\{1,\ldots,n-2\}$ without any $(i,i+1)$ subsequence.  (Note that the element after $i+1$ in the sequence cannot be $i+2$, or the original sequence contained an $(i+1,i+2)$ subsequence.)
Conversely, we construct these in the following ways:


*

*Given a permutation of $\{1,\ldots,n-1\}$ without any $(i,i+1)$ subsequence, we can insert $n$ except directly after $n-1$, giving $n$ possibilities.

*Given a permutation of $\{1,\ldots,n-2\}$ without any $(i,i+1)$ subsequence, we choose an element $i$, increase the elements greater than $i$ by $1$, and insert $(n,i+1)$ after $i$; this gives $n-1$ possibilities.
Note that methods 1. and 2. above give distinct sequences.
Thus, the number $f(n)$ of such permutations satisfies the recurrence relation $$f(n)=nf(n-1)+(n-1)f(n-2)$$ and we observe $f(1)=1$ and $f(2)=1$.
This is Sloane's OEIS A000255, where many formulas are listed, and the sequence begins:
$$
1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, 2467007773, \ldots
$$
A: Suppose there are $p_n$ permutations of the first $n$ integers without prohibited pairs
Then there are $(n-1)p_{n-1}$ permutations with exactly one prohibited pair as you have $n-1$ pairs of such integers and the rest of the permutation must not contain them
So when you get a new integer $n+1$ you can

*

*put it at the beginning of a permutation of the first $n$ integers without prohibited pairs: $p_n$ possibilities

*put it immediately after any of the integers other than $n$ in a permutation of the first $n$ integers without prohibited pairs: $(n-1)p_n$ possibilities

*put it in the middle of the prohibited pair of a permutation with exactly one prohibited pair: $(n-1)p_{n-1}$ possibilities

That gives you the recurrence
$$p_{n+1} = np_n+(n-1)p_{n-1}$$
and as Rebecca J. Stones says, this is OEIS A000255 offset
A: Inclusion-exclusion immediately yields
$$\sum_{p=0}^{n-1} {n-1\choose p} (-1)^p (n-p)!$$
which gives the sequence
$$1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457,\ldots$$
The nodes of the poset here  represent subsets $P$ of $[n-1]$ where an
element  $q\in  P$   indicates  that  $[q,q+1]$  is   present  in  the
permutation.  Hence $P$ corresponds to permutations where $[q,q+1]$ is
present, with $q\in P$, plus  possibly more adjacent pairs.  Therefore
only  $P=\emptyset$   represents  permutations  with   no  consecutive
adjacent elements.  With the weight  being $(-1)^{|P|}$ we  get weight
one  for  these.  On  the   other  hand  a  permutation  with  exactly
$R\subseteq[n-1],  R\ne\emptyset$ adjacent  pairs is  included in  all
nodes $P\subseteq R$, giving weight
$$\sum_{P\subseteq R} (-1)^{|P|} =
\sum_{p=0}^{|R|} {|R|\choose p} (-1)^p = 0,$$
producing  zero.   It  remains  to  compute  the  cardinality  of  the
permutations  represented by  a node  $P$ where  $|P|=p.$ We  list the
pairs $[q,q+1]$ where $q\in P$  in order, fusing adjacent equal values
(and removing  the duplicate)  to form  blocks, say  there are  $m$ of
them, with lengths $l_1, l_2, \ldots  l_m.$ Here we observe that $1\le
m\le p.$ We have by construction that
$$l_1-1+l_2-1+\cdots+l_m-1 = |P|=p.$$
The number  of elements that  we have  removed from the  $n$ available
ones is
$$l_1+l_2+\cdots+l_m = p + m.$$ We put the $m$ blocks back in, getting
$$n-(p+m)+m = n - p$$
components that we may then permute, thus concluding PIE.
Remark. This problem appeared at the following MSE link.
 Addendum. Note that the formula from PIE may be written as
$$n \sum_{p=0}^{n-1} {n-1\choose p} (-1)^p (n-p-1)!
- \sum_{p=0}^{n-1} {n-1\choose p} (-1)^p p (n-p-1)!$$
or 
$$n (n-1)! \sum_{p=0}^{n-1} \frac{(-1)^p}{p!}
- (n-1)! \sum_{p=1}^{n-1} \frac{(-1)^p}{(p-1)!}$$
or
$$- (-1)^{n} +  n! \sum_{p=0}^{n} \frac{(-1)^p}{p!}
+ (n-1)! \sum_{p=1}^{n-1} \frac{(-1)^{p-1}}{(p-1)!}.$$
Introducing derangement numbers
$$D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$
this becomes
$$- (-1)^n + D_n +
(n-1)! \sum_{p=0}^{n-2} \frac{(-1)^{p}}{p!}$$
or $$ - (-1)^n + D_n - (-1)^{n-1} +
(n-1)! \sum_{p=0}^{n-1} \frac{(-1)^{p}}{p!}.$$
or alternatively
$$\bbox[5px,border:2px solid #00A000]{
D_n + D_{n-1}.}$$
