Azulejos de dominó

Construcción geométrica

Un mosaico de dominó de un cuadrado de 8 × 8

En geometría , un mosaico de dominó de una región en el plano euclidiano es un mosaico de la región por dominós , formas formadas por la unión de dos cuadrados unitarios que se encuentran de borde a borde. De manera equivalente, es una coincidencia perfecta en el gráfico de cuadrícula formado al colocar un vértice en el centro de cada cuadrado de la región y conectar dos vértices cuando corresponden a cuadrados adyacentes.

Funciones de altura

Para algunas clases de mosaicos en una cuadrícula regular en dos dimensiones, es posible definir una función de altura asociando un número entero a los vértices de la cuadrícula. Por ejemplo, dibuje un tablero de ajedrez, fije un nodo con altura 0, luego para cualquier nodo hay un camino desde él. En esta ruta, defina la altura de cada nodo (es decir, las esquinas de los cuadrados) como la altura del nodo anterior más uno si el cuadrado a la derecha de la ruta de a es negro y menos uno en caso contrario.${\displaystyle A_{0}}$${\displaystyle A_{0}}$${\displaystyle A_{n+1}}$${\displaystyle A_{n}}$${\displaystyle A_{n}}$${\displaystyle A_{n+1}}$

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, tiene un mosaico de dominó. Forma un gráfico no dirigido que tiene como vértices los puntos ( x , y , z ) en la red de enteros tridimensionales , donde cada uno de esos puntos 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 la ( x, y ) plano, se eleva de forma única (una vez que se elige una altura inicial) a una trayectoria en este gráfico tridimensional . Una condición necesaria para que esta región sea enlosable es que este camino 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 trayectoria del límite, Thurston dio un criterio para la capacidad de mosaico de una región que era tanto suficiente como necesario.

Contando mosaicos de regiones

Un mosaico de dominó de un cuadrado de 8 × 8 utilizando el número mínimo de pares de borde largo a borde largo (1 par en el centro). Esta disposición también es un mosaico Tatami válido de un cuadrado de 8x8, sin cuatro fichas de dominó tocándose en un punto interno.

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

${\displaystyle \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 se reduce a cero correctamente posibles embaldosados dominó.

Un caso especial ocurre cuando se coloca en mosaico el rectángulo con n fichas de dominó: la secuencia se reduce a la secuencia de Fibonacci (secuencia A000045 en la OEIS ) ( Klarner y Pollack 1980 ) .${\displaystyle 2\times n}$error de harv: sin destino: CITEREFKlarnerPollack1980 ( ayuda )

Otro caso especial ocurre para cuadrados con m = n = 0, 2, 4, 6, 8, 10, 12, ... es

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (secuencia A004003 en la OEIS ).

Estos números se pueden encontrar escribiéndolos como el Pfaffian de una matriz simétrica sesgada cuyos valores propios se pueden encontrar explícitamente. Esta técnica se puede aplicar en muchas materias relacionadas con las matemáticas, por ejemplo, en el cálculo bidimensional clásico de la función correladora dímero-dímero en mecánica estadística .${\displaystyle mn\times mn}$

El número de teselaciones de una región es muy sensible a las condiciones de los límites y puede cambiar drásticamente con cambios aparentemente insignificantes en la forma de la región. Esto se ilustra con 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 se reemplaza por el "diamante azteca aumentado" de orden n con 3 filas largas en el medio en lugar de 2, el número de teselaciones cae al número mucho más pequeño D ( n , n ), un número de Delannoy , que solo tiene valores exponenciales. en lugar de un crecimiento superexponencial en n. Para el "diamante azteca reducido" de orden n con solo una fila central larga, solo hay un mosaico.

• Un diamante azteca de orden 4, que tiene 1024 mosaicos de dominó.

• Un posible mosaico

Tatami

Los tatami son alfombrillas japonesas en forma de dominó (rectángulo de 1x2). Se utilizan para colocar azulejos en las habitaciones, pero con reglas adicionales sobre cómo se pueden colocar. En particular, por lo general, los cruces donde se encuentran tres tatami se consideran propicios, mientras que los cruces donde se juntan cuatro son desfavorables, por lo que un mosaico de tatami adecuado es uno en el que solo tres tatami se encuentran en cualquier esquina ( Mathar 2013 ; Ruskey & Woodcock 2009 ). El problema de embaldosar una habitación irregular con tatami que se juntan tres en una esquina es NP-completo ( Erickson & Ruskey 2013 ).

Curvas de relleno de espacio degeneradas

Cualquier conjunto finito de celdas que formen una cuadrícula cuadrada regular n × n puede indexarse ​​mediante una curva de relleno de espacio seleccionada que sea consistente con los cuadrados (que hacen una recursividad de cuatro particiones de la cuadrícula de la unidad cuadrilátera), con un índice i que va de 0 a n ² -1. Geométricamente, la curva se puede dibujar como un camino a través del centro de las celdas cuadradas. Un mosaico de dominó se obtiene fusionando las celdas vecinas. El índice j de cada dominó se obtendrá mediante la función j = piso ( i  ÷  2) del índice de la cuadrícula original. La nueva curva fractales una "curva degenerada" porque es otro fractal. Ejemplos:

La " curva de relleno de espacio de Morton degenerada " produce un mosaico dominó de orientación horizontal regular; la curva está relacionada con la indexación de Geohash , donde la curva en forma de Z se transforma en una curva en forma de И.

La " curva de llenado de espacio de Hilbert degenerada " produce un sistema de mosaico aperiódico , que mezcla dominós de orientación horizontal y vertical, el 50% de cada orientación. La curva de Hilbert degenerada es isomorfa al fractal de Munkres. ^[1]

Aplicaciones en física estadística

Existe una correspondencia uno a uno entre un mosaico de dominó periódico y una configuración de estado fundamental del modelo de Ising completamente frustrado en una red periódica bidimensional. ^[2] Para ver eso, observamos que en el estado fundamental, cada placa del modelo de giro debe contener exactamente una interacción frustrada . Por lo tanto, visto desde la celosía dual , cada borde frustrado debe estar "cubierto" por un rectángulo de 1x2 , de modo que los rectángulos abarquen toda la celosía y no se superpongan, o un mosaico dominó de la celosía dual.

Ver también

• 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 de tablero de ajedrez mutilado , un rompecabezas sobre el mosaico de dominó de un subconjunto de 62 cuadrados del tablero de ajedrez
• Mecánica estadística

Referencias

1. El fractal de Munkres se define en "Teorema 44.1" en faculty.etsu.edu/gardnerr/5357/notes/Munkres-44
2. Barahona, F (1 de octubre de 1982). "Sobre la complejidad computacional de los modelos de vidrio giratorio de Ising" . Revista de Física A: Matemática y General . 15 (10): 3241–3253. Código Bibliográfico : 1982JPhA ... 15.3241B . doi : 10.1088 / 0305-4470 / 15/10/028 . ISSN  0305-4470 .

• Bodini, Olivier; Latapy, Matthieu (2003), "Generalizado Tilings con funciones Altura" (PDF) , morfismos , 7 (1): 47-68, ISSN  1.870 a 6.525 , Archivado desde el original, el 2012-02-10 , recuperada 2008-09- 08
• Erickson, Alejandro; Ruskey, Frank (2013), "La cobertura de tatami de Domino es NP-completo", Algoritmos combinatorios , Lecture Notes in Comput. Sci., 8288 , Springer, Heidelberg, págs. 140-149, arXiv : 1305.6669 , doi : 10.1007 / 978-3-642-45278-9_13 , MR  3162068 , S2CID  12738241
• Faase, F. (1998), "Sobre el número de subgráficos de expansión específicos de los gráficos GX P_n", Ars Combin. , 49 : 129-154, MR  1633083
• Hock, JL; McQuistan, RB (1984), "Una nota sobre la degeneración ocupacional de los dímeros en un espacio reticular bidimensional saturado", Discrete Applied Mathematics , 8 : 101-104, doi : 10.1016 / 0166-218X (84) 90083-0 , Señor  0739603
• Kasteleyn, PW (1961), "Las estadísticas de dímeros en una celosía. I. El número de arreglos de dímeros en una celosía cuadrática", Physica , 27 (12): 1209-1225, Bibcode : 1961Phy .... 27.1209K , doi : 10.1016 / 0031-8914 (61) 90063-5
• Kenyon, Richard (2000), "El modelo de dímero plano con límite: una encuesta", en Baake, Michael; Moody, Robert V. (eds.), Direcciones en cuasicristales matemáticos , CRM Monograph Series, 13 , Providence, RI: American Mathematical Society , págs. 307–328, ISBN 0-8218-2629-8, MR  1798998 , Zbl  1026.82007
• Kenyon, Richard; Okounkov, Andrei (2005), "¿Qué es ... un dímero?" (PDF) , Notices of the American Mathematical Society , 52 (3): 342–343, ISSN  0002-9920
• Klarner, David ; Pollack, Jordan (1980), "Azulejos dominó de rectángulos con ancho fijo", Matemáticas discretas , 32 (1): 45–52, doi : 10.1016 / 0012-365X (80) 90098-9 , MR  0588907 , Zbl  0444.05009
• Mathar, Richard J. (2013), Pavimentación de regiones rectangulares con baldosas rectangulares: revestimientos de tatami y no tatami , arXiv : 1311.6135 , Bibcode : 2013arXiv1311.6135M
• Propp, James (2005), "Lambda-determinants and dominó-tilings", Advances in Applied Mathematics , 34 (4): 871–879, arXiv : math.CO/0406301 , doi : 10.1016 / j.aam.2004.06.005 , S2CID  15679557
• Ruskey, Frank ; Woodcock, Jennifer (2009), "Contando tejas de tatami de altura fija" , Electronic Journal of Combinatorics , 16 (1): R126, doi : 10.37236 / 215 , MR  2558263
• Sellers, James A. (2002), "Dominó y productos de números de Fibonacci y Pell" , Journal of Integer Sequences , 5 (Artículo 02.1.2): 12, Bibcode : 2002JIntS ... 5 ... 12S
• Stanley, Richard P. (1985), "Sobre revestimientos dímeros de rectángulos de ancho fijo", Matemáticas aplicadas discretas , 12 : 81–87, doi : 10.1016 / 0166-218x (85) 90042-3 , MR  0798013
• Thurston, WP (1990), "Conway's Tiling Groups ", American Mathematical Monthly , Mathematical Association of America, 97 (8): 757–773, doi : 10.2307 / 2324578 , JSTOR  2324578
• Wells, David (1997), The Penguin Dictionary of Curious and Interesting Numbers (edición revisada), Londres: Penguin, p. 182, ISBN 0-14-026149-4
• Temperley, HNV ; Fisher, Michael E. (1961), "Problema de dímero en mecánica estadística - un resultado exacto", Philosophical Magazine , 6 (68): 1061–1063, Bibcode : 1961PMag .... 6.1061T , doi : 10.1080 / 14786436108243366