Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Are $1,n$ considered neighbors, originally? –  Jonathan Y. Jan 20 at 16:02
    
Yes, 1 and n are considered neighbors. –  0ana Jan 20 at 16:04
    
Are rotations of an arrangement considered to be equivalent? –  user84413 Jan 20 at 23:45
    
Not necesarily, 13524 and 14253 may be considered different. –  0ana Jan 21 at 4:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.