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.

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

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}


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.