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, let's get the answers for n=1, 2, 3, 4, 5
It is not hard to see that the answers are: 1, 2, 6, 9, 13 respectively
OK. Next, let’s talk about the Fibonacci Sequence. The standard indexing is
(F(0) = 0) (Sometimes this term is omitted)
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
With the sequence defined recursively, for n > 1, F(n)=F(n-1) + F(n-2)
-----------
Answer to the problem of a round table:
R(1)=1
R(2)=2
R(n)= F(n+1) + F(n-1) + 2, for n>2
or equivalently:
R(n)= F(n) + 2 F(n-1) + 2, for n>2
or equivalently:
R(n) = 3 F(n-1) + F(n-3) + 2, for n>2
etc.
This gives: R(i)=1, 2, 6, 9, 13, ... (i=1 , ...)
So, why is this the answer?
First, let's solve a simpler problem: n people are seated along one side of a rectangular table with n chairs. They are in a line so we use "L". They stand up and sit down. They can more one or no places. (The people on the ends of the table can exchange with the person next to them or not at all.)
L(n) are the number of ways n people can rearrange (reseat) themselves on one side of the rectangular table. It is not hard to see that:
L(1)=1, L(2)=2, L(3)=3, L(4)=5
Note that L(4) = L(3)+ L(2). Why? Start with 3 people. Add one more person to the end. If she stays in her seat, the others can swap in L(3) ways. If she swaps with the person next to her, there are two chairs used up, and the others can swap in L(2) ways. So, L(4) = L(3) + L(2). This recursion holds for all n. Either n-1 or n-2 people are able to rearrange:
L(n) = L(n-1) + L(n-2)
This is also the definition of the Fibonacci Sequence, except that the index is off by one.
L(n) = F(n+1)
Now consider the round table. Three more things can happen:
The end two people can exchange seats. This adds L(n-2) = F(n-1) new possibilities for the remaining n-2 people. Also, all can rotate left and all can rotate right. Thus 2 more possibilities are added.
So R(n) = F(n+1) + F(n-1) + 2 for n>2
QED
(Yes, this is the exact method of B. Smith. I rewrote it for a young math student who has trouble with English, so as to be as readable as possible. Cheers - SL)
Edited on August 26, 2019, 7:32 am
Same answer, different write up:
