Pleasant Permutations

Lets us call a pair of numbers with difference d problematic. Note that, $d \geq \frac{n}{2}$. This means, there are exactly n-d problematic pairs and these pairs are disjoint. A permutation is pleasant if none of these problematic pairs are adjacent.

We can now solve the problem using the principle of inclusion exclusion. Suppose we want our permuation to contain k adjacent problematic adjacent pairs. These k pairs can be chosen out of the n-d pairs in $\binom{n-d}{k}$ ways. If we consider each of the k pairs as a single entity, we must permute n-2k+ k = n-k elements among themselves. This can be done in (n-k)! ways. Finally, each of the k pairs can be ordered among themselves 2 ways, giving a total of number of ways $(n-k)! \binom{n-d}{k} 2^k$ ways.

Then by the principle of inclusion exclusion, the number of permutations without any adjacent problematic pairs is given by $\sum\nolimits_{i=0}^{n-d} (-1)^i (n-i)! \binom{n-d}{i} 2^i$.

In order to make the solution O(n), we should precalculate factorials and powers of 2 and calculate binomial coefficients in O(1).