Diamante azteca

Un diamante azteca de orden 4

En matemáticas combinatorias , un diamante azteca de orden n consiste en todos los cuadrados de una red cuadrada cuyos centros ( x , y ) satisfacen | x | + | y ​​| ≤ n . Aquí n es un entero fijo, y la red cuadrada consiste en cuadrados unitarios con el origen como vértice de 4 de ellos, de modo que tanto x como y son semienteros . ^[1]

Una de las 1024 posibles teselas de dominó de un diamante azteca de orden 4

Un mosaico de fichas de dominó de un diamante azteca de orden 50, elegido de manera uniforme al azar. Las cuatro esquinas del diamante que están fuera del área aproximadamente circular están "congeladas".

El teorema del diamante azteca establece que el número de teselas de dominó del diamante azteca de orden n es 2 ^{n ( n +1)/2} . ^[2] El teorema del Círculo Polar Ártico establece que una teselación aleatoria de un diamante azteca grande tiende a quedar congelada fuera de un cierto círculo. ^[3]

Es habitual colorear las fichas de la siguiente manera. Primero, considere la coloración del diamante en forma de tablero de ajedrez. Cada ficha cubrirá exactamente un cuadrado negro. Las fichas verticales en las que el cuadrado superior cubre un cuadrado negro se colorean de un color y las demás fichas verticales de un segundo color. Lo mismo ocurre con las fichas horizontales.

Knuth también ha definido diamantes aztecas de orden n + 1/2. ^[4] Son idénticos a los poliominós asociados con los números cuadrados centrados .

Caminos que no se cruzan

Algo que resulta muy útil para contar teselas es observar los caminos que no se intersecan a través de su grafo dirigido correspondiente . Si definimos nuestros movimientos a través de una tesela ( tesela dominó ) como

• (1,1) cuando estamos en la parte inferior de un mosaico vertical
• (1,0) donde estamos al final de un mosaico horizontal
• (1,-1) cuando estamos en la parte superior de un mosaico vertical

Luego, a través de cualquier mosaico, podemos tener estos caminos desde nuestras fuentes hasta nuestros sumideros . Estos movimientos son similares a los caminos de Schröder . Por ejemplo, considere un diamante azteca de orden 2, y después de dibujar su gráfico dirigido, podemos etiquetar sus fuentes y sumideros . son nuestras fuentes y son nuestros sumideros. En su gráfico dirigido, podemos dibujar un camino desde a , esto nos da una matriz de caminos , , ${\displaystyle a_{1},a_{2}}$ ${\displaystyle b_{1},b_{2}}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{j}}$ ${\displaystyle P_{2}}$

${\displaystyle P_{2}={\begin{bmatrix}a_{1}b_{1}&a_{2}b_{1}\\a_{1}b_{2}&a_{2}b_{2}\\\end{bmatrix}}={\begin{bmatrix}6&2\\2&2\\\end{bmatrix}}}$

donde todos los caminos desde hasta . El número de teselas para el orden 2 es ${\displaystyle a_{i}b_{j}=}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{j}}$

det ${\displaystyle (P_{2})=12-4=8=2^{2(2+1)/2}}$

Según Lindstrom-Gessel-Viennot , si dejamos que S sea el conjunto de todas nuestras fuentes y T el conjunto de todos nuestros sumideros de nuestro grafo dirigido, entonces

det número de caminos que no se intersecan de S a T. ^[5] ${\displaystyle (P_{n})=}$

Considerando el grafo dirigido del Diamante Azteca, Eu y Fu también han demostrado que los caminos de Schröder y las teselaciones del Diamante Azteca están en biyección . ^[6] Por lo tanto, encontrar el determinante de la matriz de caminos , , nos dará el número de teselaciones para el Diamante Azteca de orden n . ${\displaystyle P_{n}}$

Otra forma de determinar el número de teselaciones de un diamante azteca es utilizando matrices de Hankel de números de Schröder grandes y pequeños , ^[6] utilizando nuevamente el método de Lindstrom-Gessel-Viennot . ^[5] Encontrar el determinante de estas matrices nos da el número de caminos no intersecantes de números de Schröder pequeños y grandes , que está en biyección con las teselaciones. Los números de Schröder pequeños son y los números de Schröder grandes son , y en general nuestras dos matrices de Hankel serán ${\displaystyle \{1,1,3,11,45,\cdots \}=\{y_{0},y_{1},y_{2},y_{3},y_{4},\cdots \}}$ ${\displaystyle \{1,2,6,22,90,\cdots \}=\{x_{0},x_{1},x_{2},x_{3},x_{4},\cdots \}}$

${\displaystyle H_{n}={\begin{bmatrix}x_{1}&x_{2}&\cdots &x_{n}\\x_{2}&x_{3}&\cdots &x_{n+1}\\\vdots &\vdots &&\vdots \\x_{n}&x_{n+1}&\cdots &x_{2n-1}\\\end{bmatrix}}}$y ${\displaystyle G_{n}={\begin{bmatrix}y_{1}&y_{2}&\cdots &y_{n}\\y_{2}&y_{3}&\cdots &y_{n+1}\\\vdots &\vdots &&\vdots \\y_{n}&y_{n+1}&\cdots &y_{2n-1}\\\end{bmatrix}}}$

donde det y det donde (También es cierto que det donde esta es la matriz de Hankel como , pero comenzó con en lugar de para la primera entrada de la matriz en la esquina superior izquierda). ${\displaystyle (H_{n})=2^{n(n+1)/2}}$ ${\displaystyle (G_{n})=2^{n(n-1)/2}}$ ${\displaystyle n\geq 1}$ ${\displaystyle (H_{n}^{0})=2^{n(n-1)/2}}$ ${\displaystyle H_{n}}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{1}}$

Otros problemas de alicatado

Consideremos la forma, bloque, y podemos hacer la misma pregunta que para el diamante azteca de orden n . Como esto se ha demostrado en muchos artículos, nos referiremos a. ^[7] Dejando que la forma del bloque se denote por , entonces se puede ver ${\displaystyle 2\times n}$ ${\displaystyle 2\times n}$ ${\displaystyle B_{n}}$

El número de teselaciones de ${\displaystyle B_{n}=F_{n}}$

donde es el número de Fibonacci n y . Se entiende que es una forma que solo se puede colocar en mosaico de una manera, no hay formas. Usando la inducción , considere y que es solo una ficha de dominó donde solo hay mosaico. Suponiendo que el número de mosaicos para , entonces consideramos . Centrándonos en cómo podemos comenzar nuestro mosaico, tenemos dos casos. Podemos comenzar con nuestra primera ficha en vertical, lo que significa que nos quedamos con que tiene diferentes mosaicos. La otra forma en que podemos comenzar nuestro mosaico es colocando dos fichas horizontales una encima de la otra, lo que nos deja con que tiene diferentes mosaicos. Al sumar las dos juntas, el número de mosaicos para . ^[7] ${\displaystyle F_{n}}$ ${\displaystyle ^{th}}$ ${\displaystyle n\geq 0}$ ${\displaystyle B_{0}}$ ${\displaystyle 2\times 0}$ ${\displaystyle B_{1}}$ ${\displaystyle 2\times 1}$ ${\displaystyle F_{1}=1}$ ${\displaystyle B_{n}=F_{n}}$ ${\displaystyle B_{n+1}}$ ${\displaystyle B_{n}}$ ${\displaystyle F_{n}}$ ${\displaystyle B_{n-1}}$ ${\displaystyle F_{n-1}}$ ${\displaystyle B_{n+1}=F_{n}+F_{n-1}=F_{n+1}}$

Generando teselas válidas

Encontrar teselas válidas del diamante azteca implica la solución del problema subyacente de cobertura de conjuntos . Sea el conjunto de fichas de dominó 2X1 donde cada ficha de dominó en D puede colocarse dentro del diamante (sin cruzar sus límites) cuando no hay otras fichas de dominó presentes. Sea el conjunto de cuadrados 1X1 que se encuentran dentro del diamante y que deben cubrirse. Se puede encontrar que dos fichas de dominó dentro de D cubren cualquier cuadrado límite dentro de S, y se puede encontrar que cuatro fichas de dominó dentro de D cubren cualquier cuadrado no límite dentro de S. ${\displaystyle D=\{d_{1},d_{2},\dots ,d_{n}\}}$ ${\displaystyle S=\{s_{1},s_{2},\dots ,s_{m}\}}$

Definamos como el conjunto de fichas de dominó que cubren el cuadrado , y sea una variable indicadora tal que si se utiliza la ficha de dominó en el mosaico, y 0 en caso contrario. Con estas definiciones, la tarea de mosaico del diamante azteca puede reducirse a un problema de satisfacción de restricciones formulado como un programa de números enteros binarios: ${\displaystyle c(s_{i})\subset D}$ ${\displaystyle s_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}=1}$ ${\displaystyle i^{th}}$

${\displaystyle \min \sum _{1\leq i\leq m}0\cdot x_{i}}$

Sujeto a: para , y . ${\displaystyle \sum _{i\in c(s_{i})}x_{i}=1,}$ ${\displaystyle 1\leq i\leq m}$ ${\displaystyle x_{i}\in \{0,1\}}$

La restricción garantiza que cada cuadrado estará cubierto por una sola ficha, y el conjunto de restricciones asegura que cada cuadrado estará cubierto (sin agujeros en la cubierta). Esta formulación se puede resolver con paquetes de programación entera estándar. Se pueden construir restricciones adicionales para forzar la colocación de fichas de dominó particulares, garantizar que se use una cantidad mínima de fichas de dominó orientadas horizontal o verticalmente, o generar mosaicos distintos. ${\displaystyle i^{th}}$ ${\displaystyle s_{i}}$ ${\displaystyle m}$

Un enfoque alternativo es aplicar el algoritmo X de Knuth para enumerar teselaciones válidas para el problema.

Referencias

1. Stanley, Richard P. (1999), Combinatoria enumerativa. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press , ISBN 978-0-521-56069-6, MR  1676282, archivado desde el original el 5 de octubre de 2008 , consultado el 18 de noviembre de 2008
2. Elkies, Noam ; Kuperberg, Greg ; Larsen, Michael ; Propp, James (1992), "Matrices de signos alternos y teselas de dominó. I", Journal of Algebraic Combinatorics , 1 (2): 111–132, doi : 10.1023/A:1022420103267 , ISSN  0925-9899, ​​MR  1226347
3. Jockusch, William; Propp, James; Shor, Peter (1998), Teselas aleatorias de dominó y el teorema del círculo polar ártico , arXiv : math/9801068 , Bibcode :1998math......1068J
4. Knuth, Donald E. (2019), "Prefascículo 5c (sección 7.2.2.1, Enlaces danzantes)", El arte de la programación informática, vol. 4, pág. 93
5. Majumdar, Diptapriyo. "Algoritmos de grafos avanzados: Lema de Gessel Viennot" (PDF) . Archivado (PDF) desde el original el 5 de marzo de 2018. Consultado el 22 de abril de 2014 .
6. Eu, Sen-Peng; Fu, Tung-Shan (2005). "Una prueba simple del diamante azteca". Electron. J. Combin., 12: Artículo de investigación . The Electroninc Journal of Combinatorics: 0412041. CiteSeerX 10.1.1.214.7065 . 
7. Martinez, Megan; Kanoff, Ilene. "Domino Tiling and the Fibonacci numbers" (PDF) . Archivado (PDF) desde el original el 2016-05-03 . Consultado el 2 de marzo de 2018 .

Enlaces externos

• Weisstein, Eric W. "Diamante azteca". MundoMatemático .