La resolución de una permutación circular problema con recursividad

Question

N las personas están invitadas a una cena, y están sentados en una mesa redonda. Cada persona está sentada en una silla; hay exactamente N sillas. Por lo que cada persona tiene exactamente dos vecinos de sillas, una en la izquierda y el otro a la derecha. El anfitrión decide la reorganización de la sala de acuerdos. Una persona será feliz con el nuevo arreglo, si él puede sentarse en el inicio de su presidente o de cualquiera de sus primeros vecinos sillas.

Tenemos que encontrar la cantidad de arreglos diferentes que no son felices. Dos arreglos son considerados diferentes si hay al menos una persona que se sienta en otra silla en los arreglos.

¿Cómo puedo solucionar este problema con una relación recursiva? Ya que soy novato en el conteo, una clara explicación es necesaria.

Answer 1

Yo calculada varios cargos, para $N\le 8$, el uso de la matriz permanentes describen a continuación. Estos fueron suficientes para buscar OEIS y encontrar el encanto nombre:

OEIS A000183: el Número de los discordantes permutaciones de longitud n.

Maneras para volver a colocar n de los comensales en la mesa circular, ninguno en o junto a la cátedra original.

Una nota por Vladimir Shevelev ahí le da cuatro períodos de recurrencia no homogénea de la relación (con coeficientes no constantes), que se atribuye en una forma equivalente a K. Yamamoto.

Deje $f(n) = F(n-1) + F(n+1) + 2$ donde $F(n)$ $n$- ésimo número de Fibonacci.

Entonces, para $n\ge 7$, tenemos la recursividad:

$$ 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)] $$

Un método para calcular el permitido permutaciones

Construcción de la matriz de adyacencia $A$ del tamaño de la $N\times N$ donde:

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

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

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 el 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 el 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} = \operatorname{perm} (1/3) + \operatorname{perm} A(1/4) + \operatorname{perm} (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} (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} (1/4) = 8$ and $\operatorname{perm} (1/5) = 6$.

Therefore with $N=6$ we have $\operatorname{perm} A = 6+8+6 = 20$ permitió que "ninguna persona feliz" permutaciones.

La sintaxis para SageMath Cálculos

La permanente de un circulantes de la matriz binaria se puede encontrar utilizando varios CAS paquetes. La sintaxis de SageMath de la siguiente manera.

Construir una matriz, la primera vez que utiliza este:

sagemath: from scipy.linalg import circulant

Entonces, podemos invocar:

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

Sucesivamente más grandes matrices pueden ser procesadas por la inserción de un adicional 1, en la línea de comandos que construye A.

Answer 2

Yo sólo podía llegar a una solución para el sistema lineal (no circular) en la versión con el tiempo la complejidad de la $O(n^3)$.

Vamos $f(n,m,k,c,d)$ ($c,d\in\{0,1\}$) ser el número de colocaciones de personas $a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_m$ en las posiciones $1,2,\ldots,n$, de modo que hay exactamente $k$ feliz a la gente (lineal y no circular por el momento) entre el $a_i$ $b_1,b_2,\ldots,b_r$ están colocados, y:

1. $c=0$ para las colocaciones de s.t. $a_n$ no está colocado.
2. $c=1$ para las colocaciones de s.t. $a_n$ se coloca.
3. $d=0$ para las colocaciones de s.t. no es $i$ s.t. $b_i\to n$.
4. $d=1$ para las colocaciones de s.t. $b_1\to n$.

Deje $f(n,m,k,*,?)=mf(n,m,k,*,0)+f(n,m,k,*,1)$ arbitrarias $*$.

Deje $f(n,m,k,?,*)=f(n,m,k,0,*)+f(n,m,k,1,*)$ arbitrarias $*$.

Entonces:

$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} $

---

Como una ilustración, la fórmula de arriba cubre los casos:

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$ para $i\ne n-1$, $a_{n-1}$ no se coloca:
   $\text{if}(m>0,mf(n-1,m+1,k-1,0,1),0)$
6. $a_n\to n-1$, $a_i\to n$ para $i\ne n-1$, $a_{n-1}$ se coloca:
   $(m+1)f(n-1,m+1,k,1,1)$

7. $a_n\to \{1,\dots,n-2\}$, $a_i\to n$ para $i\ne n-1$ y el:

   una. $a_{n-1}$ no está:
   $\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}$ se coloca:
   $(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)$

Entonces la respuesta para el número de permutaciones $\sigma$, de modo que $k$ de los números de satisfacer $\sigma(i)\in \{i-1,i,i+1\}$$f(n,0,k,?,?)$.