Teselado en dominó

Domino tiling of a square

En geometría, un dominó embaldosado de una región en el Bidimensional es un teselado de la región por dominos, formas formadas por la unión de dos unit squares que se encuentran de extremo a extremo. Equivalentemente, es un perfect matching en 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 en una grilla regular en dos dimensiones, es posible definir una función de altura asociando un entero al vertices de la grilla. Por ejemplo, dibuje un tablero de ajedrez, arregle un nodo $A_{0}$ con altura 0, luego para cualquier nodo hay una ruta de $A_{0}$ a él. En esta ruta, defina 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 de lo contrario.

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

La condición de la 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ó. Él forma un grafo que tiene como vértices los puntos ( x , y , z ) en el integer lattice tridimensional, donde cada punto está conectado a cuatro vecinos: si x  + 'y 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' '& nbsp; + 1,' 'y' ',' 'z' '& nbsp; - 1), (' 'x' '& nbsp ; 1, y , z  - 1), ( x , y  + 1, z & nbsp ; + 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 three-dimensional graph. 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 alunizajes de regiones

Domino tiling of an 8×8 square using the minimum number of long-edge-to-long-edge pairs (1 pair in the center). This arrangement is also a valid Tatami tiling of an 8x8 square, with no four dominoes touching at an internal point.

El número de formas de cubrir un rectángulo $m\times n$ con dominós ${\frac {mn}{2}}$, 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 posibles efectos de dominó.

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

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

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

Estos números se pueden encontrar escribiéndolos como el Pfaffian de un $mn\times mn$ matriz antisimétrica cuyos vector propio y valor propio 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 del dimer-dimer correlator function 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 cambios aparentemente insignificantes en la forma de la región. Esto está ilustrado por el número de mosaicos de un Aztec diamond 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, la el número de ajustes cae en el número mucho más pequeño D ( n , n ), un Números de Delannoy, que tiene solo exponencial en lugar de tetración en n . Para el "diamante azteca reducido" de orden n con solo uno fila media larga, solo hay un mosaico.

• 
  An Aztec diamond of order 4, with 1024 domino tilings
• 
  One possible tiling

Tatami

Tatami 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 tatami se consideran auspiciosas, mientras que las uniones donde las cuatro se encuentran son desfavorables, por lo que un tatami apropiado es aquel donde 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).

Ver también

• Física estadística
• Gaussian free field, 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 domino 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 ..
• 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 .