n objects in circle with fixed placement; number of permutations made only of transpositions

Question

The problem is given as follows:

There are n people sitting in n seats, with n $\geq$ 3 Any person can either stay in the same seat, or move to an adjacent seat. How many ways can this be done? A diagram is given with the problem and it is clear that the seats are considered fixed and rotations which end up in different seats are not considered equivalent.

---

Clearly the identity permutation is one. There are two rotations of one place, one clockwise and one counterclockwise. These three permutations exist for every n.

All other permutations fulfilling the conditions must consist solely of collections of 2-cycles or transpositions.

For n = 3 there are three possible transpositions, so the total number of permissible permutations for n = 3 is 6

For n = 4 we can have four possible transpositions, (AB)(BC)(CD) and (DA) If one of these transpositions is chosen and the other two elements are left unmoved, we have four choices so there are four possible permutations. If two transpositions are used, the first necessarily restricts the choice of the second so there are two possible permutations.

Thus there are 4 + 2 + 3 = 9 permissible permutations for n = 4

For n = 5 we can have one transposition, or two transpositions and a singleton left. There are five choices of single transpositions. If we use two transpositions there are five choices of singleton left over. There is a total of 5 + 5 + 3 = 13 permissible permutations for n = 5

I tried various combinatorics methods. A try at stars and bars, but placement of the bars is problematic; transpositions cannot overlap. For k transpositions, n - k objects of which k are pairs and n - 2k are singletons. Placement is problematic again because the pairs take two seats.

I was wondering if there might be a Fibonacci pattern as the number of permissible permutations grows rapidly. It occurred to me that perhaps odd and even n could be studied separately, doing induction on adding 2 each step.

I've been puzzling over this for a few days and have a few ideas but nothing has jelled yet

Answer 1

For such arrangements $f(n)$ of $n$ people in a straight line the $n^{\text{th}}$ person may either take seat $n$ in $f(n-1)$ ways or swap with person $n-1$ in $f(n-2)$ ways so

$$f(n) = f(n-1)+f(n-2)\tag{1}$$

with $f(1)=1$ and $f(2)=2$.

In a circle there are $g(n)$ seatings. Person $n$ may take their own seat in $f(n-1)$ ways, swap with person $n-1$ in $f(n-2)$ ways, swap with person 1 in $f(n-2)$ ways or is part of a clockwise or anticlockwise rotation of all people by 1 seat. So, for $n\ge 3$ we have

$$g(n)=f(n-1)+2f(n-2)+2$$ $$\implies g(n)=f(n)+f(n-2)+2\tag{2}$$

since $f(n)$ is the sequence

$$1,2,3,5,8,13,21,34,\ldots$$

$g(n)$ is for $n\ge 3$ (using $g(1)=1$ and $g(2)=2$)

$$1,2,6,9,13,20,31,49,\ldots$$

Extra:

By rearranging $(2)$ for $f(n)$ and substituting into $(1)$ we have a recurrence for $g(n)$ only

$$g(n)-f(n-2)-2=(g(n-1)-f(n-3)-2)+(g(n-2)-f(n-4)-2)$$ $$\implies g(n)=g(n-1)+g(n-2)-2\tag{3}$$

which is true for $n\ge 5$ and $g(1)=1,\, g(2)=2,\, g(3)=6,\, g(4)=9$.