There are $n$ people seated on a circular table which has seats numbered from 1 to $n$ clockwise. Let $k$ be a fixed integer, between $2$ and $n$ (both inclusive).
The people can change their seats. There are two types of moves permitted:
- Each person moves to the next seat clockwise.
- Only the ones in seats $1$ and $k$ exchange their seats.
Determine, as a function of $n$ and $k$, the number of possible configurations of people in the table that can be attained by using a sequence of permitted moves.
My thoughts:
If condition (2) is not there then answer is obviously $n$; but if (2) is imposed on each arrangement of (1), then, you can further rotate that particular arrangement $n$ times to get new arrangements. I'm not sure how to get the closed form of $f(n,k)$.
For small values of $n$, such as 3, 4, etc. it is easy to calculate by manual counting; but for larger values it's becoming a difficult task. Also, I think this could maybe be a problem involving some combinatorial recursion.
The operations as given in the question have a fixed swapper of two persons and a moving table (the "table" being the circle of people). Now let the swapper move and fix the table; we lose only a position factor in this (which will be reintroduced later).
Sliding the swapper around the table, we see that the people split into $\gcd(n,k-1)$ disjoint cycles of $\frac n{\gcd(n,k-1)}$ people each (here illustrated for $n=18,k=5$):
Within each cycle, because we can swap any two people who are adjacent in the cycle, we can achieve any permutation – $\left(\frac n{\gcd(n,k-1)}\right)!$ ways. Since we have $\gcd(n,k-1)$ independent cycles, we can achieve $\left(\left(\frac n{\gcd(n,k-1)}\right)!\right)^{\gcd(n,k-1)}$ arrangements with the modified operations.
However, the original operations allow us to move the $\gcd(n,k-1)$ cycles around the circle, which the modified operations do not allow. Since any cycle can occupy a fixed position on the circle, there are $\gcd(n,k-1)$ distinct ways to align the cycles to the circle, the missing position factor from before. Finally $$f(n,k)=\gcd(n,k-1)\left(\left(\frac n{\gcd(n,k-1)}\right)!\right)^{\gcd(n,k-1)}$$