Solving a circular permutation problem with recursion

Question

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.

Answer 1

I computed several counts, for $N\le 8$, using the matrix permanents outlined below. These were enough to search OEIS and find the charmingly named:

OEIS A000183: Number of discordant permutations of length n.

Ways to reseat n diners at circular table, none in or next to original chair.

A note by Vladimir Shevelev there gives a four-term inhomogeneous recurrence relation (with nonconstant coefficients), attributed in an equivalent form to K. Yamamoto.

Let $f(n) = F(n-1) + F(n+1) + 2$, where $F(n)$ is the $n$-th Fibonacci number.

Then, for $n\ge 7$, we have the recursion:

$$ a(n) = (-1)^n[4n+f(n)] + \frac{n}{(n-1)}\cdot[(n+1)a(n-1) + 2\cdot(-1)^nf(n-1)] $$ $$- \frac{2n}{(n-2)}\cdot[(n-3)a(n-2) + (-1)^nf(n-2)] + \frac{n}{(n-3)}[(n-5)a(n-3) + 2\cdot(-1)^{n-1}f(n-3)] + \frac{n}{(n-4)}[a(n-4) + (-1)^{n-1}f(n-4)] $$

A method for computing the allowed permutations

Construct the adjacency matrix $A$ of size $N\times N$ where:

$$ A_{ij} = \begin{cases} 0 & \text{ if } i-j \equiv -1,0,1 \mod N \\ 1 & \text{otherwise} \end{cases} $$

Then the count of allowed "no person happy" permutations is the permanent of circulant $(0,1)$-matrix $A$.

Permanents can be computed in various ways. One is expansion by (unsigned) cofactors using the entries of any row (or column), which might satisfy the request for "a recursive relation". We illustrate this with some sample computations below. A more sophisticated algorithm is used by CAS packages like SageMath, and mistakes in my hand calculations were illuminated by comparisons with those results.

It seems to be a part of the folklore that permanents of circulant $(0,1)$ matrices can be exactly computed using recurrence relations, as for example the 1982 paper Some remarks on the permanents of circulant (0,1) matrices by Eades, Praeger, and Seberry. See especially the final section of that paper, on cases of circulant binary matrices with few zero entries, to which a "complement expansion" is applied. This gives hope that a simple recurrence relation, as sought in this Question, can be found.

Sample computations by cofactor expansion

Clearly there are no allowed solutions if $N \le 3$, since no one can move far enough from the original seats to be unhappy. For $N = 4$ we have a unique solution, as can be seen from the entries of our adjacency matrix:

$$ A = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} $$

Here's sketch of the permanent computation for $N=6$. We have:

$$ A = \begin{bmatrix} 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \end{bmatrix} $$

For each nonzero entry in the first row, we obtain three $5\times 5$ minors:

$$ A(1|3) = \begin{bmatrix} 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{bmatrix} $$

$$ A(1|4) = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{bmatrix} $$

$$ A(1|5) = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \end{bmatrix} $$

So $\operatorname{perm} A = \operatorname{perm} A(1|3) + \operatorname{perm} A(1|4) + \operatorname{perm} A(1|5)$. [NB: I mistakenly thought that, by symmetry, these three cofactors would be equal; it is not the case (see below).]

Expanding $\operatorname{perm} A(1|3)$ again across its bottom row, etc.:

$$ \operatorname{perm} \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} + \operatorname{perm} \begin{bmatrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{bmatrix} = 1 + 5 $$

In similar fashion one gets $\operatorname{perm} A(1|4) = 8$ and $\operatorname{perm} A(1|5) = 6$.

Therefore with $N=6$ we have $\operatorname{perm} A = 6+8+6 = 20$ allowed "no person happy" permutations.

Syntax for SageMath Computations

The permanent of a circulant binary matrix can be found using several CAS packages. The syntax for SageMath follows.

To construct such a matrix, I first used this:

sagemath: from scipy.linalg import circulant

Then we can invoke:

sagemath: A = matrix(circulant([0,0,1,1,1,0])); A
[0 0 1 1 1 0]
[0 0 0 1 1 1]
[1 0 0 0 1 1]
[1 1 0 0 0 1]
[1 1 1 0 0 0]
[0 1 1 1 0 0]

sagemath: A.permanent()
20

Successively larger matrices can then be processed by inserting an additional 1, into the commandline that constructs A.

Answer 2

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:

1. $c=0$ for the placements s.t. $a_n$ is not placed.
2. $c=1$ for the placements s.t. $a_n$ is placed.
3. $d=0$ for the placements s.t. there is no $i$ s.t. $b_i\to n$.
4. $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:

1. $a_n\to n$:
   $f(n-1,m,k-1,?,?)$
2. $a_{n-1}\to n$, $a_n\to n-1$:
   $f(n-1,m,k-2,0,1)$
3. $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)$
4. $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)$
5. $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)$
6. $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)$

7. $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,?,?)$.