Teselado en dominó

En geometría, un teselado en dominó de una región en el espacio bidimensional es un recubrimiento de la región mediante dominós, piezas formadas por la unión de dos cuadrados iguales lado a lado. Equivalentemente, es un pareado perfecto sobre el gráfico de celosía formado al colocar un vértice en el centro de cada cuadrado de la región y conectando dos vértices cuando corresponden a cuadrados adyacentes.

Funciones de altura

Para algunas clases de mosaicos sobre una rejilla en dos dimensiones, es posible definir una función de altura asociando un entero a cada vértice de la rejilla. Por ejemplo, sobre un tablero de ajedrez, se asigna el nodo $A_{0}$ con altura 0, y para cualquier nodo hay una ruta desde $A_{0}$ hasta él. En esta ruta, se define la altura de cada nodo $A_{n+1}$ (es decir, las esquinas de los cuadrados) como la altura del nodo anterior $A_{n}$ más uno si el cuadrado a la derecha de la ruta de $A_{n}$ a $A_{n+1}$ es negro, y menos uno en caso contrario.

Se pueden encontrar más detalles en Kenyon y Okounkov (2005).

Condición de altura de Thurston

William Thurston (1990) describe una prueba para determinar si una región simplemente conectada, formada como la unión de cuadrados unitarios en el plano, puede recubrirse con un mosaico en dominó. Forma un grafo que tiene como vértices los puntos (x,y,z) en una rejilla tridimensional de valores enteros, donde cada punto está conectado a cuatro vecinos: si x + y es par, entonces (x,y,z) está conectado a (x + 1,y,z + 1), (x - 1,y,z + 1), (x,y + 1, z - 1), y (x,y - 1,z - 1), mientras que si x + y es impar, entonces (x,y,z) está conectado a (x + 1,y,z - 1), (x 1,y,z - 1), (x,y + 1,z + 1), y (x,y - 1,z + 1). El límite de la región, visto como una secuencia de puntos enteros en el plano (x,y), se levanta de forma única (una vez que se elige una altura de inicio) a una ruta en este grafo tridimensional. Una condición necesaria para que esta región sea enlosable es que esta ruta debe cerrarse para formar una curva cerrada simple en tres dimensiones, sin embargo, esta condición no es suficiente. Utilizando un análisis más cuidadoso de la ruta límite, Thurston dio un criterio para determinar la idoneidad de una región que era suficiente y necesaria.

Recuento de teselados de regiones

El número de formas de cubrir un rectángulo de $m\times n$ con ${\frac {mn}{2}}$ dominós, calculado independientemente por Temperley y Fisher (1961) y Kasteleyn (1961), viene dado por

\prod _{j=1}^{\lceil {\frac {m}{2}}\rceil }\prod _{k=1}^{\lceil {\frac {n}{2}}\rceil }\left(4\cos ^{2}{\frac {\pi j}{m+1}}+4\cos ^{2}{\frac {\pi k}{n+1}}\right).

Cuando ambos m y n son impares, la fórmula reduce correctamente a cero los posibles recubrimientos en dominó.

Se produce un caso especial cuando se embaldosa el rectángulo $2\times n$ con n dominós: la secuencia se reduce a la sucesión de Fibonacci (sucesión A000045 en OEIS) (Klarner y Pollack, 1980).

Otro caso especial se produce para cuadrados con m = n = 0, 2, 4, 6, 8, 10, 12, ... cuyos números de soluciones distintas coinciden con

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (sucesión A004003 en OEIS).

Estos números se pueden encontrar escribiéndolos como el pfaffiano de una matriz antisimétrica $mn\times mn$ cuyos vectores y autovalores se pueden encontrar explícitamente. Esta técnica se puede aplicar en muchos temas relacionados con las matemáticas, por ejemplo, en el cálculo clásico bidimensional de la función de correlación dimer-dimer en física estadística.

El número de ajustes de una región es muy sensible a las condiciones de contorno y puede cambiar drásticamente con modificaciones aparentemente insignificantes en la forma de la región. Esto queda ilustrado por el número de mosaicos de un diamante azteca de orden n, donde el número de mosaicos es 2^(n + 1)n/2. Si esto es reemplazado por el "diamante azteca aumentado" de orden n con 3 filas largas en el medio en lugar de 2, el número de ajustes cae al número mucho más pequeño D (n,n), un número de Delannoy, que tiene solo carácter exponencial en lugar de tetración en n. Para el "diamante azteca reducido" de orden n con solo una fila media larga, solo existe un mosaico.

Un diamante azteca de orden 4, con 1024 posibles teselados en dominó
Uno de estos teselados

Tatamis

Los tatamis son tapetes japoneses en forma de dominó (rectángulo de 1x2). Se usan para colocar mosaicos en habitaciones, pero con reglas adicionales sobre cómo se pueden colocar. En particular, típicamente, las uniones donde se encuentran tres tatamis se consideran favorables, mientras que las uniones donde se unen cuatro esquinas se consideran desfavorables, por lo que una disposición de tatamis apropiada es aquella en la que solo tres tatamis se juntan en cualquier esquina (Mathar, 2013;Ruskey y Woodcock, 2009). El problema de embaldosar una habitación irregular con un tatami que se une a una esquina es NP-completo(Erickson y Ruskey, 2013).

Véase también

Física estadística
Campo libre Gaussiano, el límite de escala de la función de altura en la situación genérica (por ejemplo, dentro del disco inscrito de un gran diamante azteca)
Problema del tablero de ajedrez mutilado, un acertijo relacionado con el mosaico de dominó de un subconjunto de 62 casillas del tablero de ajedrez

Referencias

Bodini, Olivier; Latapy, Matthieu (2003), «Generalized Tilings with Height Functions», Morfismos 7 (1): 47-68, ISSN 1870-6525, archivado desde el original el 10 de febrero de 2012, consultado el 30 de diciembre de 2017 ..
Erickson, Alejandro; Ruskey, Frank (2013), «Domino tatami covering is NP-complete», Combinatorial algorithms, Lecture Notes in Comput. Sci. 8288, Springer, Heidelberg, pp. 140-149, MR 3162068, doi:10.1007/978-3-642-45278-9_13 .
Faase, F. (1998), «On the number of specific spanning subgraphs of the graphs G X P_n», Ars Combin. 49: 129-154, MR 1633083 .
Hock, J. L.; McQuistan, R. B. (1984), «A note on the occupational degeneracy for dimers on a saturated two-dimenisonal lattice space», Discrete Applied Mathematics 8: 101-104, MR 0739603, doi:10.1016/0166-218X(84)90083-0 .
Kasteleyn, P. W. (1961), «The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice», Physica 27 (12): 1209-1225, Bibcode:1961Phy....27.1209K, doi:10.1016/0031-8914(61)90063-5 ..
Kenyon, Richard (2000), «The planar dimer model with boundary: a survey», en Baake, Michael; Moody, Robert V., eds., Directions in mathematical quasicrystals, CRM Monograph Series 13, Providence, RI: American Mathematical Society, pp. 307-328, ISBN 0-8218-2629-8, MR 1798998, Zbl 1026.82007 .
Kenyon, Richard; Okounkov, Andrei (2005), «What is … a dimer?», Notices of the American Mathematical Society 52 (3): 342-343, ISSN 0002-9920 ..
Klarner, David; Pollack, Jordan (1980), «Domino tilings of rectangles with fixed width», Discrete Mathematics 32 (1): 45-52, MR 588907, Zbl 0444.05009, doi:10.1016/0012-365X(80)90098-9 ..
Mathar, Richard J. (2013), Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings, arXiv:1311.6135 .
Propp, James (2005), «Lambda-determinants and domino-tilings», Advances in Applied Mathematics 34 (4): 871-879, arXiv:math.CO/0406301, doi:10.1016/j.aam.2004.06.005 ..
Ruskey, Frank; Woodcock, Jennifer (2009), «Counting fixed-height Tatami tilings», Electronic Journal of Combinatorics 16 (1): R126, MR 2558263 .
Sellers, James A. (2002), «Domino tilings and products of Fibonacci and Pell numbers», Journal of Integer Sequences 5 (Article 02.1.2) ..
Stanley, Richard P. (1985), «On dimer coverings of rectangles of fixed width», Discrete Applied Mathematics 12: 81-87, MR 0798013, doi:10.1016/0166-218x(85)90042-3 .
Thurston, W. P. (1990), «Conway's tiling groups», American Mathematical Monthly (Mathematical Association of America) 97 (8): 757-773, JSTOR 2324578, doi:10.2307/2324578 ..
Wells, David (1997), The Penguin Dictionary of Curious and Interesting Numbers (revised edición), London: Penguin, p. 182, ISBN 0-14-026149-4 ..
Temperley, H. N. V.; Fisher, Michael E. (1961), «Dimer problem in statistical mechanics-an exact result», Philosophical Magazine 6 (68): 1061-1063, doi:10.1080/14786436108243366 .

Datos: Q21042776
Multimedia: Domino tilings / Q21042776