# 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?

-

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.
Could you explain in more details the recursive relationship for $a(n)$? – Kim Jong Un Sep 5 '14 at 4:09