10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you solve the derangements problem? The one such that no person returns to his own chair? $\endgroup$ – user1537366 Dec 15 '14 at 14:25
  • $\begingroup$ It's problem G of the following contest: algo.codemarshal.org/contests/acm-icpc-2014-dhaka-live $\endgroup$ – user1537366 Dec 16 '14 at 10:05
  • $\begingroup$ Note that while the set of "no person happy" permutations does not form a subgroup of $S_n$ (the group of all permutations), since in particular the identity permutation makes everyone happy, but it is closed under taking inverses. $\endgroup$ – hardmath Dec 16 '14 at 15:42
  • $\begingroup$ @hardmath I've finally found a reference for this: Section 6 of sciencedirect.com/science/article/pii/0012365X87900021 gives a complete proof which can be extended for the solution of the contest problem. $\endgroup$ – user1537366 Dec 20 '14 at 6:27
  • $\begingroup$ A working link for the contest problem is bubt-cse.edu.bd/?icpcpg=prblmSet (problem G). $\endgroup$ – user1537366 Dec 20 '14 at 6:28
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It's hard to follow, esp. in the case $m\neq n$. How exactly does "$c$ only [depend] on $n,m,t$"? Since we are studying when $k=0$, it seems that a discussion of how the recursion behaves on these cases. Perhaps a worked example $f(6,m,0)$ would clear things up? $\endgroup$ – hardmath Dec 21 '14 at 16:37
  • $\begingroup$ @hardmath Sorry, my original solution could not be made to work. Moreover, now I still don't know how to do the circular case. $\endgroup$ – user1537366 Dec 23 '14 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.