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

## 2 Answers

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