How many permutations avoid previous adjacencies? This question was asked by another user. It was closed and deleted, taking with it an answer of mine that I think people might find useful. So I'm reposting the question, and my answer (lightly edited). Seven friends went to see a movie. At the time of interval they went away. In how many ways when they come back can they sit that no two previously adjacent people will sit together?

The answer, and much more, is available here at the Online Encyclopedia of Integer Sequences.

With $n$ friends (instead of 7), the number of ways, $a(n)$, satisfies the recurrence, $$a(n) = (n+1)a(n-1)-(n-2)a(n-2)-(n-5)a(n-3)+(n-3)a(n-4)$$ with $a(0)=a(1)=1$, $a(2)=a(3)=0$. The closest thing to a closed-form formula is $$a(n)=n!+\sum_{k=1}^n(-1)^k\sum_{t=1}^k{k-1\choose t-1}{n-k\choose t}2^t(n-k)!$$ There's an asymptotic expansion $${a(n)\over n!}\sim e^{-2}\bigl(1-2n^{-2}-(10/3)n^{-3}-6n^{-4}-(154/15)n^{-5}\bigr)$$

Of course, the question as posed doesn't ask for a general formula or asymptotics, just for $a(7)$, which is 646.