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.

I was going to generalize an easy counting problem and I ended up not being able to solve it:

In how many ways can $n$ people $1,\dots,n$ be seated around a round table if person $i$ refuses to sit next to person $i+1$, for all $i\in\{1,\dots,n-1\}$, and person $n$ refuses to sit next to person 1.

I realized that I have to have $n\geq5$ in order to have at least one solution.

What I have done:

  1. it's very tempting to use the principle of inclusion and exclusion, but I'm not sure how to exactly do it, since it gets really messy very soon. Any help with this will be appreciated.

  2. Something else that I did was using recursion, but all I'm getting is a lower bound, since I'm not able to completely analyse it:

    If $n-1$ people are seated around a table in $a_{n-1}$ ways, one can place $n$ among them except for the $4$ places around $1$ and $n-1$. But then we are not counting the cases like: $$\dots,2,n,3,\dots$$ All it says is that $a_n \geq (n-5)a_{n-1}$.

    I assume I should connect it to the case when $i$ refuses to sit next to $i+1$ for $i\in\{1,\dots,n-1\}$. But still not sure how.

  3. It is straight forward to calculate that $a_5=2$.

PS: Is there any relation to the Menage's problem?

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

I think this is Number of ways of arranging the numbers 1..n in a circle so that adjacent numbers do not differ by 1 mod n at the Online Encyclopedia of Integer Sequences. There is a link there to Number of polygons that can be formed from n points on a circle, no two adjacent which is half the number we want. At the latter page there is a (rather complicated, nonlinear, 5th order) recurrence, and an asymptotic expansion in inverse powers of $n$. For the sequence at hand, this starts out $$a_n/(n-1)!\sim e^{-2}(1-(4/n))$$

share|improve this answer
1  
Linked in the reference above: reports.stanford.edu/pub/cstr/reports/cs/tr/80/829/… (see esp. page 3) –  leonbloy Jun 25 '12 at 13:57
    
amazing, thanks so much. –  Keivan Jun 25 '12 at 23:49
add comment

A quick and dirty asymptotic: assuming a random arrangement, the probabilty that the person at seat $k$ finds a legal neighbour at seat $k+1$ is $P(e_k)=(n-3)/(n-1)$. The event that the arrangement is legal is $P(e_1 \cap e_2 \cdots)$. The events $e_k$ are not independent, but we can assume that asympotically we can write

$$P(e_1 \cap e_2 \cdots) = P(e_k)^n=\left(\frac{n-3}{n-1}\right)^n = \left(1- \frac{2}{n} -\frac{2}{n^2} + O(n ^{-3})\right)^n \to e^{-2}$$

So $$a_n \to (n-1)! \, e^{-2}$$

share|improve this answer
add comment

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.