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)}$?
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
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 $$
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}.}$$