Not as easy as it looks!

The idea is to use the Principle of Inclusion-Exclusion , but the solution is somewhat intricate. The best way to understand the solution is to look at a particular example.

More generally, let $S$ be the set of all permutations of the numbers 1, 2, $\dots$ , $n$ , and for $1 \le i \le n - 1$ , let $A_{i,i + 1}$ denote the subset of permutations where $i$ and $i + 1$ are adjacent. We want to count the number of permutations where $i$ and $i + 1$ are never adjacent, and by PIE, this number is $\begin{aligned} &|S| - |A_{1,2}| - |A_{2,3}| - \dots - |A_{n - 1,n}| \\ &\quad + |A_{1,2} \cap A_{2,3}| + |A_{1,2} \cap A_{3,4}| + \dots + |A_{1,2} \cap A_{n - 1,n}| \\ &\quad - |A_{1,2} \cap A_{2,3} \cap A_{3,4}| - \dotsb. \end{aligned}$ So, we must understand what the intersections of these sets look like.

As an example, let $n = 8$ . Consider the intersection $A_{1,2} \cap A_{2,3} \cap A_{3,4} \cap A_{5,6} \cap A_{6,7}.$ For a permutation in this intersection, 1 is next to 2, 2 is next to 3, 3 is next to 4, 5 is next to 6, and 6 is next to 7. Thus, the numbers 1, 2, 3, 4 form one chain, and the numbers 5, 6, 7 form another chain. So permutations in this intersection include $(4, 3, 2, 1, 8, 5, 6, 7)$ and $(7, 6, 5, 1, 2, 3, 4, 8)$ .

More generally, consider an intersection of $k$ of the sets $A_{i,i + 1}$ . Just as we saw in the example above, there will be a number of chains in this intersection. Let $t$ be the number of such chains. (Note that this number $t$ is not uniquely determined by $k$ .) Then for the PIE calculation, for a fixed value of $k$ , instead of trying to compute the number of elements in each intersection, then summing over all possible intersections of $k$ sets, we will count the number of permutations with $t$ chains (that arise from the intersection of $k$ sets).

Let $c_1$ , $c_2$ , $\dots$ , $c_t$ be the number of elements in the first chain, second chain, and so on, up until the $t$ th chain. Then the first chain is determined by $c_1 - 1$ adjacent pairs, the second chain is determined by $c_2 - 1$ adjacent pairs, and so on. Hence, $\sum_{i = 1}^t (c_i - 1) = \sum_{i = 1}^t c_i - t = k,$ so $\sum_{i = 1}^t c_i = t + k.$ This says there are $t + k$ elements among all $t$ chains, so there are $n - t - k$ elements that are not included in any chains. Let's call these "single elements".

To construct a permutation with $t$ chains, we start by writing the numbers 1, 2, $\dots$ , $n$ in a row, and deciding which numbers go in chains, and which numbers become single elements. First, we decide the number of elements in each chain. We use the equation $\sum_{i = 1}^t (c_i - 1) = k.$ Each value $c_i - 1$ is a positive integer. Then by stars and bars, the number of solutions to the equation above is $\dbinom{k - 1}{t - 1}$ .

When we write out the numbers 1, 2, $\dots$ , $n$ , they will form $t$ chains and $n - t - k$ single elements, in some order. There are $\dbinom{n - k}{t}$ ways to order them. We then let $c_1$ be the number of elements in the first chain, $c_2$ the number of elements in the second chain, and so on. Every number from 1 to $n$ has now been assigned as part of a chain or a single element.

There are now $(n - k)!$ ways to order the $t$ chains and $n - t - k$ single elements. Finally, for each chain, we can order it forwards or backwards, so there are $2^t$ different ways to order the elements in the $t$ chains. Putting everything together, we get that the number of permutations we seek is $n! + \sum_{k = 1}^n (-1)^k \sum_{t = 1}^n \binom{k - 1}{t - 1} \binom{n - k}{t} 2^t (n - k)!.$

The recursion that I have used is

[a 0 = a 1 = 1, a 2 = a 3 = 0), and $a_n = (n+1)a_{n-1} - (n-2)a_{n-2} - (n-5)a_{n-3} + (n-3)a_{n-4}$ for all (n \geq 4]

If you guys want to check the OEIS listing , try here