Here's a pretty tricky recursive formula I am trying to find.
As in the title, the question is:
Assume $n$ people are seated in a circle. In how many ways can their seating be re-arranged (one person per seat!) so no person moves more than one seat away from their original place (any person can move one seat to their left, right or stay in his/her seat)? Any two re-arrangements that are equivalent by rotation are counted as identical.
Find a recursive formula and initial cases.
EDIT: A person can stay in his/her original seat.
Let's start calculating the initial cases:
$ n=1 $ then there is only one possible arrangement, so $ a_1=1$
$ n=2 $ then there are two arrangements: $<1,2>$ and $<2,1>$ but since the personals sit in a circle, those cases are actually equal, then $ a_2=1$
$ n=3 $ then the possible arrangements are:
$<1,2,3>,<1,3,2>, <2,1,3>, <2,3,1>, <3,1,2>, <3,2,1>$
And after removing the dups, we are left with:
$<1,2,3> <1,3,2>$
And so on and on. Well, to make things "quicker" I used an algorithm I created that outputs this recursive values, so here's the list: $a_1 = 1; dups:0$
$a_2 = 1; dups:1$
$a_3 = 2; dups:4$
$a_4 = 6; dups:3$
$a_5 = 11; dups:2$
$a_6 = 18; dups:2$
$a_7 = 29; dups:2$
$a_8 = 47; dups:2$
$a_9 = 76; dups:2$
It is easy to see that the first 4 sequences has random duplicates number, but for $a_i, i >=5 $ the duplicates are always 2.
Here I am stuck. Iv'e tried any technique I know, but I cant figure out how to bring the information Iv'e gathered into a recursive formula.
The only reasonable idea I had, is to split the recursion:
First, supply those 4 initial cases:
$ for 1<=i<=5 a_1 = 1, a_2=1, a_3 = 2, a_4 = 6, a_5 = 11 $
For $ i > 5, a_n = a_{n-1}+a_{n-2} $
But I am not sure such definition is even legal.