¿De cuántas maneras puede azulejo un rectángulo de NxM con L polyominos?

Question

Me encontré con un problema que me ha estado molestando:

De cuántas maneras puede el azulejo de una NxM rectángulo con L-polyominos?

La L formas pueden ser de cualquier tamaño, siempre y cuando ellos no son líneas.

Una aclaración:
$L(1,m) = 0$,
$L(2,2) = 0$,
$L(2,3) = 2$,
$L(2,4) = 2$,
$L(3,3) = 0$...

He tratado de resolverlo mediante la recursividad (la única manera que sé cómo), dividiendo el NxM cuadrícula en 2 redes más pequeñas, pero que no tiene en cuenta muchas de las posibilidades.

Resolver el problema a través de algoritmos es bastante fácil (espero :P). Aquí están algunos de los valores que obtengo:

$ \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\[0.3em] 0 & 0 & 2 & 2 & 2 & 6 \\[0.3em] 0 & 2 & 0 & 20 & 64 & 234 \\[0.3em] 0 & 2 & 20 & 110 & 752 & 4522 \\[0.3em] 0 & 2 & 64 & 752 & 7720 & 84846 \\[0.3em] 0 & 6 & 234 & 4522 & 84846 & 1557970 \end{bmatrix}$

Espero que tenga sentido: L(1,1) es en la parte superior izquierda, y L(6,6) está en la parte inferior derecha. Obviamente sus simétricos en diagonal.

Answer 1

(EDITADO) Para el caso de $2 \times m$, me parece la repetición es $$ L(2,m) = 2 \sum_{j=0}^{m-3} L(2,j)$$ where $L(2,0) = 1$ y la solución es % $ $$L(2,m) = \sum_r \dfrac{9-3r-2r^2}{29 r^m}$la suma sobre la tres raíces $r$ $2 z^3+z-1$ (aproximadamente $.58975$ y $-.29488 \pm .87227 i$). Casos con $N > 2$ van a ser más complicado. Esencialmente usted quiere mirar todas las posibilidades de lo que ocurre en un extremo de la red. Pero incluso para $N=3$ hay muy pocas posibilidades.

Answer 2

Esto principalmente es una reformulación, pero que parece útil en la sustitución de la regla global (sólo en forma de L polyominoes) con una local. El problema es equivalente a la siguiente:

¿De cuántas maneras distintas puede llenar un $M\times N$ cuadrícula con estos tres fichas (rotaciones y reflexiones están permitidos) si cada punto de color azul debe ser adyacente a un punto rojo y viceversa?

Esta formulación puede ser utilizado para obtener una relación de recursividad para el número de maneras en una fila determinada puede ser llenado con la parte superior e inferior de las fronteras, donde cada frontera es una lista de blanco, rojo y azul bordes; es decir, se puede derivar una $3^M \times 3^M$ de la matriz de transferencia.