Formas de llenar un $n\times n$ cuadrado con $1\times 1$ cuadrados y $1\times 2$ rectángulos

Question

Se me ocurrió esta pregunta cuando estaba mirando la pared de mi dormitorio. No estoy seguro de si lo estoy preguntando correctamente, pero es lo que más o menos tengo:

Entonces, ¿cuántas formas (patrón) que hay para llenar un $n\times n:n\in\mathbb{Z}_{n>0}$ cuadrado con sólo $1\times 1$ cuadrados y $1\times 2$ ¿Rectángulos?

Por ejemplo, para un $2\times 2$ cuadrado:

• Cuatro $1\times 1$ cuadrados; 1 vía.

• Dos $1\times 1$ cuadrados y uno $1\times 2$ rectángulo; $4$ formas totales, ya que podemos girarlo para obtener un patrón diferente.

• Dos $1\times 2$ rectángulos; 2 formas en total: colocados horizontal o verticalmente.

$\therefore$ Hay un total de $1+4+2=\boxed{7}$ formas de llenar un $2\times 2$ cuadrado.

Entonces, me pregunto si hay una fórmula general para calcular las formas de llenar un $n\times n$ cuadrado.

Gracias.

Answer 1

Un recuento manual para $n=3$ produce $131$ formas, y una búsqueda de $1,7,131$ produce Secuencia OEIS A028420 el "número de tilings de monómero-dímero de un $n\times n$ tablero de ajedrez". La entrada no proporciona una fórmula (por lo que es probable que no se conozca ninguna), pero sí algunas referencias.

Answer 2

Si sólo ha utilizado $1\times2$ rectángulos, entonces es lo mismo que encontrar el número de coincidencias en el $m \times n$ gráfico de rectángulo, y una fórmula para ello ha sido dada por Kastelyn:

$$ \sqrt{\left|\prod_{j=1}^{m}\prod_{k=1}^{n} \left(2 \cos \frac{\pi j}{m+1} + 2i\cos \frac{\pi k}{n+1}\right)\right|}$$

Para ello, se ha asignado el número a la raíz cuadrada del determinante de una matriz de adyacencia ponderada del gráfico.

Si incluye $1 \times 1$ cuadrados, esencialmente hay que encontrar la suma sobre todos los subgráficos (piense en colocar un $1\times 1$ cuadrado como borrar ese vértice) de la $m \times n$ gráfico, y para cada subgrafo, el enfoque determinista todavía funciona, creo, pero podría no tener una forma cerrada agradable.

Puede encontrar una buena exposición para el $1\times 2$ caso en el primer capítulo aquí: http://users.ictp.it/~pub_off/lectures/lns017/Kenyon/Kenyon.pdf

Answer 3

Sin embargo, probablemente podamos dar algunos límites superiores e inferiores. Sea $t_n$ son las posibles formas de embaldosar un $n\times n$ de la manera que usted describió. En cada plaza, podemos tener $5$ posibilidades: o bien un $1\times 1$ cuadrado, o $4$ tipos de $1\times 2$ rectángulos que van hacia arriba, derecha, abajo o izquierda. Esto le da el límite superior $t_n \leq 5^{n^2}$ .

Para el límite inferior, considere un $2n\times 2n$ rectángulo, y dividirlo en $n^2$ $2\times 2$ empezando por la parte superior izquierda y poniendo un $2\times 2$ cuadrado, poniendo otro $2\times 2$ cuadrado a su derecha y así sucesivamente... Para cada uno de estos $2\times 2$ cuadrados, tenemos $5$ posibles formas distintas de alicatar. Esto da el límite inferior $t_{2n} \geq 7^{n^2}$ . Obviamente, $t_{2n+1} \geq t_{2n},\,n \geq 1$ y por lo tanto $t_n \geq 7^{\lfloor \frac{n}{2}\rfloor ^2}$ .

Por lo tanto, \begin{align} 7^{\lfloor \frac{n}{2}\rfloor ^2} \leq t_n \leq 5^{n^2}, \end{align} o aproximadamente (si $n$ es par), \begin{align} (7^{1/4})^{n^2} \leq t_n \leq 5^{n^2}. \end{align} BTW, $7^{1/4} \geq 1.6$ . Así que, al menos sabemos $\log t_n \in \Theta(n^2)$ .

Nota: Hacer el $3\times 3 $ para el límite inferior, obtenemos $(131)^{1/9} \geq 1.7$ que es ligeramente mejor.

Answer 4

Dos comentarios:

1 Si sólo se tienen en cuenta los rectángulos de 1x2, el problema se conoce como el problema de las fichas de dominó. Puedes encontrar la respuesta aquí: http://en.wikipedia.org/wiki/Domino_tiling#Counting_tilings_of_regions

2 En el caso de un tablero de ajedrez (y creo que se puede generalizar a los cuadrados de lado par), hay pocas cosas que se sepan sobre el caso con 2 cuadrados de 1x1 y el dominó.

Si los dos cuadrados se colocan sobre dos cuadrados del tablero del mismo color, es imposible completar el mosaico, mientras que si los 2 cuadrados se colocan en colores opuestos el teorema de Gomory dice que siempre es posible completar el mosaico (pero creo que no dice de cuántas maneras).