Restricted Permutations

This is a tough problem. We can view this as a problem of generating all permutations, removing everything that has two consecutively placed elements, then removing everything that has three consecutively placed elements, adding back in the overlap between two and three consecutively placed elements permutations, ad infinitum.

This is inclusion exclusion, and we shall encode a consecutive run as a bunch of $\circ$ s. For instance, $12354687 \equiv 1\circ\circ54687$ . Let $\delta(\pi)$ be the number of $\circ$ in $\pi$ , then we want our generating function to satisfy $f(z) = \sum_{\pi} (-1)^{\delta(\pi)} z^{|\pi|}$

This can be done by setting $\circ = -1$ in the construction $f(z,\circ) = P\left(\frac{z}{1 - z\circ}\right)$ where $P(z) = \sum_k k! z^k$ counts the permutations. The desired solution is $[z^n] f(z,1) = [z^n] \sum_k k! \left(\frac{z}{1 + z}\right)^k$

This OGF expands to $z+z^2+3 z^3+11 z^4+53 z^5+309 z^6+2119 z^7+16687 z^8+148329 z^9+1468457 z^{10}+16019531 z^{11}+190899411 z^{12}+2467007773 z^{13}+34361893981 z^{14}+513137616783 z^{15}+O\left(z^{16}\right)$ so the solution is $\boxed{513137616783}$ .