Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.