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

• Could you explain in more details the recursive relationship for $a(n)$? – Kim Jong Un Sep 5 '14 at 4:09
• @Kim, sorry, I was just quoting the OEIS page, not presenting my own work. There may be some reference on that page. – Gerry Myerson Sep 5 '14 at 5:50
• this can be solved easier then the approach u used. try the case for 5 friends, then u can generalize for odd n – Randin Mar 10 '18 at 4:48
• @Randin, show me. – Gerry Myerson Mar 10 '18 at 11:17

when they return the friend in first seat can only have 8 of the other friends sitting next to him .once one of those sits in seat two , that friend now have 6 to chose from ect so probability is (8/9)(7/8)(6/7)(5/6)(4/5)(3/4)(2/3)(1/2)

• The question asks for 'how many ways' this can happen, not the probability. – Toby Mak Mar 10 '18 at 7:23
• yep I realized thgat after I posted it . it's still neat but should I delete it? – Randin Mar 10 '18 at 7:25
• Just edit your question. – Toby Mak Mar 10 '18 at 7:26
• or delete my answer? – Randin Mar 10 '18 at 8:05
• tobymak 39 can this be solved with combinatorics? – Randin Mar 10 '18 at 8:07