Diamante azteca

En matemática combinatoria , un diamante azteca de orden n consta de todos los cuadrados de un retículo cuadrado cuyos centros ( x , y ) satisfacen | x | + | y | ≤ n . Aquí n es un número entero fijo, y el retículo cuadrado consta de cuadrados unitarios con el origen como vértice de 4 de ellos, de modo que tanto x como y son semientos . ^[1]

El teorema del diamante azteca establece que el número de mosaicos dominó del diamante azteca de orden n es 2 ^{n ( n +1) / 2} . ^[2] El teorema del Círculo Polar Ártico dice que un mosaico aleatorio de un gran diamante azteca tiende a congelarse fuera de un círculo determinado. ^[3]

• 

  Un diamante azteca de orden 4, con 1024 mosaicos de dominó.

• 

  Un posible embaldosado.

• 

  Un mosaico en forma de rombo de un hexágono elegido uniformemente al azar, con los mosaicos "congelados" representados en blanco. (Teorema del Círculo Polar Ártico.)

Es común colorear las baldosas de la siguiente manera. Primero considere un color de tablero de ajedrez del diamante. Cada mosaico cubrirá exactamente un cuadrado negro. Azulejos verticales donde el cuadrado superior cubre un cuadrado negro, está coloreado en un color y los otros azulejos verticales en un segundo. Lo mismo ocurre con las baldosas horizontales.

Caminos que no se cruzan

Algo que es muy útil para contar teselaciones es mirar los caminos que no se cruzan a través de su correspondiente gráfico dirigido . Si definimos nuestros movimientos a través de un mosaico ( mosaico dominó ) para ser

• (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áfica dirigida podemos etiquetar sus fuentes y sumideros . son nuestras fuentes y son nuestros sumideros. En su grafo dirigido, podemos trazar una trayectoria desde que , esto nos da una matriz de ruta , ,${\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 de a . El número de teselaciones para el pedido 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 sea ​​el conjunto de todos nuestros sumideros de nuestro grafo dirigido, entonces

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

Teniendo en cuenta el gráfico 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 . ^[5] Por lo tanto, encontrar el determinante de la matriz de ruta , , nos dará el número de mosaicos para el diamante azteca de orden n .${\displaystyle P_{n}}$

Otra forma de determinar el número de teselaciones de un Diamante Azteca es usando matrices de Hankel de números de Schröder grandes y pequeños , ^[5] usando el método de Lindstrom-Gessel-Viennot nuevamente. ^[4] Encontrar el determinante de estas matrices nos da el número de trayectorias que no se cruzan de números de Schröder pequeños y grandes , que está en biyección con las teselaciones. Los números pequeños de Schröder son y los números grandes de Schröder 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^{2(n+1)/2}}$${\displaystyle (G_{n})=2^{2(n-1)/2}}$${\displaystyle n\geq 1}$${\displaystyle (H_{n}^{0})=2^{2(n-1)/2}}$${\displaystyle H_{n}}$${\displaystyle x_{0}}$${\displaystyle x_{1}}$

Otros problemas de mosaico

Considere la forma, el bloque y podemos hacer la misma pregunta que para el Diamante Azteca de orden n . Como esto ha sido probado en muchos artículos, nos referiremos a. ^[6] 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 número de Fibonacci y . Se entiende que es una forma que solo se puede colocar en mosaico de una manera, de ninguna manera. Usando inducción , considere y eso es solo una ficha de dominó donde solo hay baldosas. Suponiendo el número de teselaciones para , entonces consideramos . Centrándonos en cómo podemos comenzar nuestro mosaico, tenemos dos casos. Podemos comenzar con nuestro primer mosaico vertical, lo que significa que nos quedamos con el que tiene diferentes mosaicos. La otra forma en que podemos comenzar nuestro mosaico es colocando dos mosaicos horizontales uno encima del otro, lo que nos deja con que tiene${\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}}$diferentes teselaciones. Al sumar los dos, el número de teselaciones para . ^[6]${\displaystyle B_{n+1}=F_{n}+F_{n-1}=F_{n+1}}$

Generando teselaciones válidas

Encontrar teselaciones válidas del diamante azteca implica la solución del problema subyacente de la cobertura del conjunto . Sea el conjunto de dominós 2X1 donde cada dominó en D puede colocarse dentro del diamante (sin cruzar sus límites) cuando no hay otros dominós presentes. Sea el conjunto de cuadrados de 1X1 que se encuentran dentro del diamante que debe cubrirse. Se pueden encontrar dos dominós dentro de D para cubrir cualquier cuadrado límite dentro de S, y cuatro dominós dentro de D se pueden encontrar para cubrir 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}\}}$

Defina como el conjunto de dominó que cubre el cuadrado , y sea ​​una variable indicadora tal que si se usa el dominó en el mosaico y 0 en caso contrario. Con estas definiciones, la tarea de embaldosar el diamante azteca puede reducirse a un problema de satisfacción de restricciones formulado como un programa entero binario:${\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 el cuadrado estará cubierto por una sola baldosa, y la colección de restricciones asegura que cada cuadrado estará cubierto (sin agujeros en la cubierta). Esta formulación se puede resolver con paquetes de programación de enteros estándar. Se pueden construir restricciones adicionales para forzar la colocación de dominós particulares, asegurar que se use un número mínimo de dominós orientados 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 las teselaciones válidas para el problema.

enlaces externos

• Weisstein, Eric W. "Diamante azteca" . MathWorld .

Referencias

{{reflist | refs = ^{[5] [4] [6]}

1. Stanley, Richard P. (1999), Combinatoria enumerativa. Vol. 2 , Cambridge Studies in Advanced Mathematics, 62 , Cambridge University Press , ISBN 978-0-521-56069-6, MR  1676282 , archivado desde el original, el 2008-10-05 , recuperada 2008-11-18
2. Elkies, Noam ; Kuperberg, Greg ; Larsen, Michael ; Propp, James (1992), "Matrices de signo alterno y teselaciones 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), Tilings dominó aleatorios y el teorema del círculo polar ártico , arXiv : math / 9801068 , Bibcode : 1998math ...... 1068J
4. Majumdar, Diptapriyo. "Algoritmos de gráficos avanzados: Lema de Gessel Viennot" (PDF) . Archivado (PDF) desde el original el 5 de marzo de 2018 . Consultado el 22 de abril de 2014 .
5. Eu, Sen-Peng; Fu, Tung-Shan (2005). "Una simple prueba del diamante azteca". Electrón. J. Combin., 12: Documento de investigación . The Electroninc Journal of Combinatorics: 0412041. CiteSeerX 10.1.1.214.7065 . 
6. Martínez, Megan; Kanoff, Ilene. "Domino Tiling y los números de Fibonacci" (PDF) . Archivado (PDF) desde el original el 3 de mayo de 2016 . Consultado el 2 de marzo de 2018 .