Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

up vote 2 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|improve this answer
1  
Could you explain in more details the recursive relationship for $a(n)$? –  Kim Jong Un Sep 5 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 at 5:50

Your Answer

 
discard

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.