4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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))$$

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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