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?

First, consider the related problem, where the table is not round, so there are two people each sitting at a table end. Let S(n) be the number of ways people can behave on a table of length n. Look at the person sitting at one end of a table. There are two things she can do: 

1. She can sit still. Then, the number of ways the remaining people can then arrange themselves is S(n-1).

2. She can switch places with her nearest neighbour. Then, the number of ways the remaining people can then arrange themselves is S(n-2). 

So    S(n) = S(n-1) + S(n-2)    also S(1) = 1 and S(2) = 2. So we get the Fibonacci sequence shifted by 1 in the independent variable. For instance, we can write S(n) in terms of the golden ratio: 

S(n-1) = ( p^n - (1-p)^n ) / sqr(5)   where p is the golden ratio = (sqr(5) + 1)/2

_____________________

Now, let C(n) be the answer for a round table with n people.Pick two neighbouring chairs at random. There are four ways their occupants might behave.

1. They might change places. In which case the number of ways the remaining players might move is S(n-2)

2. They might remain in place. Again, the number of ways the remaining players might move is S(n-2)

3. They might both move one space in the same direction. Then, everyone else at the table has to follow their example. This gives 2 cases, each for moving clockwise or counterclockwise. 

3. One of them could stay still, while the other changes places with his remaining neighbour. This can happen in 2S(n-3) ways. 

4. Both might change places with their nearest neighbour. This can happen in S(n-4) ways

Adding, we get    C(n) = 2S(n-2) + 2 + 2S(n-3) + S(n-4) = 2( F(n-1) + F(n-2) + 1 ) + F(n-3)

Which we can express in terms of p if that is more convenient. 

For example:

C(4) = 2( F(3) + F(2) + 1 ) + F(1) = 2(2+1+1) +1 = 9   and

C(9) = 2( F(8) + F(7) + 1 ) + F(6) = 2(21+13+1) + 8 = 78

Edited on August 18, 2019, 6:10 pm

Posted by FrankM on 2019-08-18 18:06:09