Solving a circular permutation problem with recursion N people are invited to a dinner party, and they are sitting at a round table. Each person is sitting on a chair; there are exactly N chairs. So each person has exactly two neighboring chairs, one on the left and the other on the right. The host decides to shuffle the sitting arrangements. A person will be happy with the new arrangement if he can sit on his initial chair or either of his initial neighboring chairs.
We have to find the number of different arrangements such that no people are happy. Two arrangements are considered different if there is at least one person sitting on a different chair in the arrangements.
How can I solve this problem with a recursive relation? Since I'm novice in counting, a clear explanation is needed.
 A: I could only come up with a solution for the linear (non-circular) version with time complexity $O(n^3)$.
Let $f(n,m,k,c,d)$ ($c,d\in\{0,1\}$) be the number of placements of people $a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_m$ into the positions $1,2,\ldots,n$ so that there are exactly $k$ happy people (linear and non-circular at the moment) among the $a_i$, all $b_1,b_2,\ldots,b_r$ are placed, and:


*

*$c=0$ for the placements s.t. $a_n$ is not placed.

*$c=1$ for the placements s.t. $a_n$ is placed.

*$d=0$ for the placements s.t. there is no $i$ s.t. $b_i\to n$.

*$d=1$ for the placements s.t. $b_1\to n$.


Let $f(n,m,k,*,?)=mf(n,m,k,*,0)+f(n,m,k,*,1)$ for arbitrary $*$.
Let $f(n,m,k,?,*)=f(n,m,k,0,*)+f(n,m,k,1,*)$ for arbitrary $*$.
Then:
$f(n,m,k,0,0)=f(n-1,m,k-1,0,?)+\text{if}(m>1,(m-1)f(n-1,m,k,0,?),0)+mf(n-1,m,k,1,?)$
$f(n,m,k,0,1)=f(n-1,m-1,k,?,?)$
$\begin{align}
f(n,m,k,1,0)&=f(n-1,m,k-1,?,?)+f(n-1,m,k-2,0,1)\\
&\quad+mf(n-1,m+1,k-1,0,1)+f(n-1,m+1,k-1,0,0)\\
&\quad+\text{if}(m>0,mf(n-1,m+1,k-1,0,1),0)+(m+1)f(n-1,m+1,k,1,1)\\
&\quad+\text{if}(m>0,m(mf(n-1,m+1,k,0,1)+f(n-1,m+1,k,0,0)),0)\\
&\quad+(m+1)(mf(n-1,m+1,k,1,1)+f(n-1,m+1,k,1,0))
\end{align}
$

As an illustration, the formula above covers the cases:


*

*$a_n\to n$:$f(n-1,m,k-1,?,?)$

*$a_{n-1}\to n$, $a_n\to n-1$:$f(n-1,m,k-2,0,1)$

*$a_{n-1}\to n$, $a_n\to \{1,\ldots,n-2\}$, $b_i\to n-1$:$mf(n-1,m+1,k-1,0,1)$

*$a_{n-1}\to n$, $a_n\to \{1,\ldots,n-2\}$, No $b_i\to n-1$:$f(n-1,m+1,k-1,0,0)$

*$a_n\to n-1$, $a_i\to n$ for $i\ne n-1$, $a_{n-1}$ is not placed:$\text{if}(m>0,mf(n-1,m+1,k-1,0,1),0)$

*$a_n\to n-1$, $a_i\to n$ for $i\ne n-1$, $a_{n-1}$ is placed:$(m+1)f(n-1,m+1,k,1,1)$

*$a_n\to \{1,\dots,n-2\}$, $a_i\to n$ for $i\ne n-1$ and:
a. $a_{n-1}$ is not placed:$\text{if}(m>0,m(mf(n-1,m+1,k,0,1)+f(n-1,m+1,k,0,0)),0)$
b. $a_{n-1}$ is placed:$(m+1)(mf(n-1,m+1,k,1,1)+f(n-1,m+1,k,1,0))$

$f(n,m,k,1,1)=f(n-1,m,k-1,?,1)+\text{if}(m>1,(m-1)f(n-1,m,k,?,1),0)+f(n-1,m,k,?,0)$
Then the answer for the number of permutations $\sigma$ so that $k$ of the numbers satisfy $\sigma(i)\in \{i-1,i,i+1\}$ is $f(n,0,k,?,?)$.
