Circular permutations - $n$ sitting at a round table without repeating neighbors 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. 
 A: 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}

