Cuenta las maneras de llenar un tablero$4\times n$ con dominó

Question

Después de resolver este problema de SPOJ (recuento de las formas para llenar un 4xn junta con 2x1 dominó), he encontrado una solución diferente, mientras que la búsqueda en internet.

Esta solución utiliza la relación de recurrencia $f(n) = f(n-1)+5f(n-2)+f(n-3)-f(n-4)$ donde $f(n)$ indica el número de maneras de llenar las $4\times n$ junta con $2 \times 1$ fichas de dominó.

No entiendo cómo alguien se de que tipo de relación (no sé casi nada de la combinatoria o de relaciones de recurrencia), pero creo que entiendo algo. El $f(n-1)$ término viene de la observación de que no hay una única forma de llenar la última columna y la $5f(n-2)$ término viene de la observación de que hay 5 diferentes maneras de llenar las dos últimas columnas.

Pero no veo en donde los términos $f(n-3)-f(n-4)$ provienen. Así que tengo dos preguntas, la primera es donde estos términos provienen de y segundo me gustaría pedirte una referencia para aprender la combinatoria y de relaciones de recurrencia.

Puede usted ayudarme? Gracias de antemano.

-editar-

Para mi la solución que se usa un número binario para representar lo que las configuraciones de la i-ésima columna era válido. Por ejemplo 1001 declara que las filas 1 y 4 están bloqueados en la i-ésima fila porque en el (i-1)th hay una horizontal domino en que posiciones. He calculado todas las transiciones válidas tales números binarios podría ir a (lo hice a mano para todos los números binarios de 0000 a 1111). Entonces recibí una función que he programado utilizando programación dinámica y una técnica llamada máscara de bits para representar los números binarios como los números enteros. La función es:

$f(i,máscara) = \begin{cases} 0 &\mbox{if } i = n, mask \neq 0 \\ 1 & \mbox{if } i = n, mask = 0. \\ \sum f(i+1,mask') &\mbox{else} \end{casos}$

Donde mask' es tomado a partir del conjunto de todas válidas máscaras de donde la máscara podría transición, también i=n significa la primera columna fuera de la junta como yo consideraba 0-indexación. El código para el que está aquí (esto en realidad no es mío, es de un compañero, pero es exactamente la misma idea).

Answer 1

Hay ocho maneras en las que un $4\times n$ baldosas pueden comenzar, se muestra y el nombre en la foto de abajo. Vamos a contar el número de cada tipo de inicio de configuración y agregar los resultados a obtener $f(n)$.

Los tipos a través de Correo son fáciles. Cualquier $4\times (n-1)$ mosaico puede extenderse a dar un $4\times n$ suelo de baldosas, y que no hay otras maneras de obtener un "tipo a" $4\times n$ suelo de baldosas. Así que hay $f(n-1)$ "tipo a" $4\times n$ apuntados. Del mismo modo, hay $f(n-2)$ tipo B $4\times n$ apuntados, y $f(n-2)$ así como de cada uno de los tipos C, D, y E. Que la $f(n-1)+4f(n-2)$ hasta la fecha.

Apuntados con configuraciones iniciales, F, G y H son un poco más difícil de contar. Primero a definir algunos de los útiles de notación.

Deje $f_T(k)$ representan el número de $4\times k$ mosaicos de tipo T, donde T es un conjunto de configuraciones iniciales. Que nos permite decir a partir de lo que tenemos encima de que $$f(n)=f(n-1)+4f(n-2)+f_{\{F,G,H\}}(n)\textrm.$$ We just have to figure out $f_{\{F,G,H\}}(n)$ in terms of $f$.

Claramente $f_{\{F,G,H\}}(n)=f_{\{F\}}(n)+f_{\{G\}}(n)+f_{\{H\}}(n)$; vamos a calcular cada término por separado. También toma nota del hecho de que $f(k)=f_{\{A,B,C,D,E,F,G,H\}}(k)$.

Ahora, en el recuento. Vamos a ver el tipo de F en primer lugar.

Un "tipo F" $4\times (n)$ mosaico es siempre de configuración F extendido por un "tipo B" o "tipo F" $4\times (n-2)$ mosaico que tiene su centro izquierda domino eliminado. Por lo $f_F(n)$ es exactamente el número de $4\times (n-2)$ "tipo B" o "tipo F" apuntados, es decir, $f_F(n)=f_{\{B,F\}}(n-2)$. (El tipo B y F apuntados son exactamente los que tienen un centro de la izquierda domino a quitar.)

Un tipo "G" mosaico es G extendido por un mosaico de tipo a, D, o H, con la parte superior izquierda de domino eliminado. Por lo $f_G(n)=f_{\{A,D,H\}}(n-2)$. (A, D, y H son el mosaico con una parte superior izquierda de domino.)

Un tipo "H" mosaico es H extendido por un mosaico de tipo a, C o G, con la parte inferior izquierda de domino quitado, por lo $f_H(n)=f_{\{A,C,G\}}(n-2)$. (A, C, y G son el mosaico de tipos con una parte inferior izquierda de domino.)

La sustitución de estos últimos tres expresiones en la anterior ecuación muestra los rendimientos

$\begin{align*} f(n)&=f(n-1)+4f(n-2)+f_{\{B,F\}}(n-2)+f_{\{A,D,H\}}(n-2)+f_{\{A,C,G\}}(n-2)\\ &=f(n-1)+4f(n-2)+f_{\{A,B,C,D,F,G,H\}}(n-2)+f_{\{A\}}(n-2)\\ &=f(n-1)+4f(n-2)+f(n-2)-f_{\{E\}}(n-2)+f_{\{A\}}(n-2)\\ &=f(n-1)+5f(n-2)+f_{\{A\}}(n-2)-f_{\{E\}}(n-2) \end{align*}$

Afortunadamente, a y E son los más sencillos de los patrones, y sabemos de nuestros cálculos iniciales (que hicimos antes de adoptar la notación de subíndice en $f$$f_{\{A\}}(n-2)= f(n-3)$$f_{\{E\}}(n-2)= f(n-4)$. Estos cálculos finales de dar la recurrencia de la relación se le preguntó acerca de: $$f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)\textrm.$$

Voy a dejar que alguien sugieren buenas referencias para el aprendizaje de estas técnicas y acaba de decir que la experiencia ayuda. El centésimo es mucho más rápido para averiguar que el primero!

Answer 2

Yo no estoy seguro de manera intuitiva se puede explicar esta fórmula recursiva por sí mismo (y no creo que hay una explicación fácil y sin entrar en numerosos casos), pero he querido darle un enfoque general que permite derivar tales expresiones recursivas para cualquier mosaico problema $m\times n$.

En primer lugar, quería considerar un problema un poco diferente: ¿cuántos "conectado" apuntados en $m\times n$. Por "conectados" me refiero a la forma que cada dos consecutivos columnas están conectados al menos una baldosa. Vamos a llamar a nosotros esta función $g(n)$.

Queremos considerar $g(n)$, principalmente por dos razones:

1. Debe ser mucho más fácil para derivar, en parte debido al hecho de que las primeras baldosas determinará el resto de las baldosas, y en parte debido a que el segundo punto.

2. Va a ser periódica, es decir, hay algunos que no periódica parte $g(1),\dots,g(N)$, y luego hay un periódico "cola": para $k\ge 1$: $g(N+k)=g(N+k+T)$ para algunos fijos $T$.

La segunda propiedad nos permite derivar $f$ facilidad de $g$. De hecho, por cada mosaico deje $k\ge 1$ ser el número máximo de manera que la primera $k$ columnas están conectadas. A continuación, para cada $k$ cada posible baldosas pueden ser construidos como la conexión de un mosaico en el primer $k$ columnas y, a continuación, cualquier suelo de baldosas en el resto. En otras palabras, por cada $m,n$: $$f(n)=g(1)f(n-1)+g(2)f(n-2)+\dots+g(n)f(0) \tag{1}$$ donde $f(0)=1$.

Ahora, si $g$ tiene un valor distinto de cero periódico de la cola, entonces la expresión (1) crecerá con $n$, pero podemos considerar (1) para dos valores de $n$$n-T$, y restando el uno del otro, vamos a obtener una expresión fija número finito de términos. Incluso podemos escribir esta expresión de forma explícita, donde $g()$ $N$ no periódica los términos y plazo,$T$: $$f(n)=g(1)f(n-1)+\dots+g(T-1)f(n-T+1)+[g(T)+1]f(n-T)+[g(T+1)-g(1)]f(n-T-1)+\dots+[g(T+N)-g(N)]f(n-T-N) \tag{2}$$.

Let's look at how it works for different smaller values of $m$.

Tiles on $1\times n$: $m=1$. The number of connected tilings on $1\times n$ ($g(n)$) equals: $0,1,0,0,0,\dots$. Here $N=2$, $T=1$, but the tail is all zeros, so we do not need (2) to eliminate the tail. (1) gives us: $f(n)=f(n-2)$ with two initial terms $f(0)=1,f(1)=0$.

Tiles on $2\veces n$: $m=2$. $g(n\ge 1)$ equals: $1,1,0,0,0,\puntos$. Indeed, there are no connected tilings on $2\times n$ for $n\ge 3$. Once again, $N=2$ and $T=1$ with zero tail. (1) gives us $f(n)=f(n-1)+f(n-2)$ with initial terms $f(0)=1,f(1)=1$. This is just Fibonacci numbers. BTW, if we used (2), we would obtain another recursive sequence for Fibonacci numbers: $f(n)=2f(n-1)-f(n-3)$ with initial terms $f(0)=1,f(1)=1,f(2)=2$.

Tiles on $3\veces n$: $m=3$. Here where it gets interesting, because it is the first time we will have a non-zero $g$-tail. $g(n)=0$ for odd $n$. $g(2)=3$: ⨅ ⨆ and ≡. $g(4)=g(6)=\dots=2$ (assume first that horizontal tile connecting the first two columns is top or bottom and construct the rest of connected tiling in unique way). So, $g(n)$ is $0,3,0,2,0,2,\dots$. Now, $N=2$ and $T=2$ and we have to use (2): $f(n)=4f(n-2)-f(n-4)$.

Finally, tiles on $4\veces n$: $m=4$. First, we need to show that $g(n)$ for $n\ge 1$ equals $1,4,2,3,2,3,\dots$. The first two values (non-periodic part) is given (among 5 tilings of $4\times 2$ only one is disconnected). For $n>2$ consider three possible combinations of horizontal/vertical tiles covering the first column:

|    --   --
|    |    --
--   |    |
--   --   |

and show that each leads to a unique connected covering, and only two of them work for odd $n$. In this case (2) gives us: $f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)$.

Answer 3

La respuesta está aquí: A127864 o A077917 .

La fórmula real es:$f(n) = f(n-1) + 4 f(n-2) + 2 f(n-3)$. La secuencia es:$1, 5, 11, 33, \dots$.