6

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.

Community
  • 1
0ana
  • 165

1 Answers1

1

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}

Community
  • 1
ogerard
  • 1,583