A group of n people sit at a circular table. They all stand and then sit back down in their original chair or in one next to it. In how many ways can this be done?
I recall seeing a version of this problem that asks this question for people seated in a straight line of chairs. Let L(n) be the number of ways for the straight line of n people to rearrange themselves according to the puzzle.
The person on the front end either stays put and the other n-1 people are rearranged or the person on the front end trades seats with his only adjacent person and the other n-2 people are rearranged.
This implies L(n)=L(n-1)+L(n-2). There is only one way to seat a line of one chair, L(1)=1 and only two ways to seat a pair of chairs, L(2)=2. Then L(n) is the Fibonacci function.
Back to the problem as stated. Assume there are at least three people. Pick a chair, that person can either stay where he is, trade with the chair on his left, or trade with the chair on his right. In each case the other people will rearrange themselves like in the linear version of the problem.
This makes for L(n-1)+L(n-2)+L(n-2) possible rearrangements, which simplifies to L(n)+L(n-2). But there are two more possible arrangements which take advantage of the chairs being in a circle, everybody moves one chair left and everybody moves one chair right. Then the total number of a group of n (n>=3) people can rearrange themselves in the circle is L(n)+L(n-2)+2, where L(n) is the Fibonacci function.
Solution
