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.