6
$\begingroup$

I hope this isn't a duplicate - the problem is to find the number of ways of sitting $n$ people (who initially were sitting in the order $1, 2, \dots,n$, with $1$ and $n$ being neighbors) at a round table so that no two people that were neighbors initially are neighbors again. I understand that if there were no restrictions there were $(n-1)!$ different ways to arrange them. If the place of a person matters, for $n \leq 4$ I don't get any solution, for $n = 5$ I get $10$ ways, for $n = 6$, $84$ ways, for $n = 7$, $630$ ways and for $n = 8$ I get $5168$ solutions using an algorithm based on a adjacency matrix. Making that algorithm was easy comparing to finding a relation between n and the results I got (which are hopefully correct).

My way of thinking was to subtract from $(n-1)!$ a number equal to the bad combinations as reflected here arrangement of NOT sitting together but I get a negative number even for $n = 5$, for which I know I already have $10$ solutions. If the place doesn't matter and $13524$ and $14253$ are considered equivalent, then for $n = 5$ I only get one solution. It's been a long time since I studied combinatorics and I don't seem to find the right way to wrap my mind around this, so I'd appreciate any help.

$\endgroup$
5
  • $\begingroup$ Are $1,n$ considered neighbors, originally? $\endgroup$ Jan 20, 2014 at 16:02
  • $\begingroup$ Yes, 1 and n are considered neighbors. $\endgroup$
    – 0ana
    Jan 20, 2014 at 16:04
  • $\begingroup$ Are rotations of an arrangement considered to be equivalent? $\endgroup$
    – user84413
    Jan 20, 2014 at 23:45
  • $\begingroup$ Not necesarily, 13524 and 14253 may be considered different. $\endgroup$
    – 0ana
    Jan 21, 2014 at 4:17
  • $\begingroup$ @0ana : 13524 and 14253 are not related by a rotation but by a reversal. $\endgroup$
    – ogerard
    Feb 10, 2015 at 12:01

1 Answer 1

1
$\begingroup$

The sequence you wanted to compute is A089222, which starts n=5 : 10, 36, 322, ... but the more fundamental one is A078603, where you confound 2 arrangements if they differ only by a rotation of the table, and starts n=5 : 2, 6, 46, 354, ... and then there is A002816 where the orientation (clockwise/counterclockwise) does not count either : 1, 3, 23, 177, ... .

If you follow the links I give to the Encyclopedia of integer sequences, you will find a few references, articles and formulas (notably one of the binomial inclusion/exclusion type) about this problem and a few of its interpretations.

The question is little more involved that it seems.

I believe two problems you had when you tried to find all cases for n>=5 is that you were starting with one fixed point ( $(n-1)!$ possibilities) ) and that you subtracted impossibilities based on $n!$ configurations. Also in your implementation of a computer algorithm, you may have not exhausted all the conditions/positions to exclude, and you would have been better off looking only for the configurations starting with 1 (i.e. up to rotation).

For reference, for n=6 the 6 arrangements starting with 1 are

{1, 3, 5, 2, 6, 4}, {1, 3, 6, 4, 2, 5},

{1, 4, 2, 6, 3, 5}, {1, 4, 6, 2, 5, 3},

{1, 5, 2, 4, 6, 3}, {1, 5, 3, 6, 2, 4}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .