diamante azteca

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 consta de cuadrados unitarios con el origen como vértice de 4 de ellos, de modo que tanto x como y son semienteros . ^{[ 1 ]}

El teorema del diamante azteca establece que el número de recubrimientos de dominó del diamante azteca de orden n es 2 ^{n ( n +1)/2} . ^{[ 2 ]} El teorema del círculo polar ártico dice que un recubrimiento aleatorio de un diamante azteca grande tiende a quedar congelado fuera de un círculo determinado. ^{[ 3 ]}

Es común colorear las fichas de la siguiente manera. Primero, consideremos un patrón de tablero de ajedrez para el diamante. Cada ficha cubrirá exactamente un cuadrado negro. Las fichas verticales, donde el cuadrado superior cubre un cuadrado negro, se colorean de un color, y las demás fichas verticales de un segundo color. De manera similar para 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 .

Algo que resulta muy útil para contar teselaciones es observar los caminos que no se intersecan a través de su grafo dirigido correspondiente . Definimos los vértices del grafo para que se encuentren en los bordes izquierdo y derecho de los cuadrados, centrados verticalmente (por lo que${\displaystyle y=k+{\frac {1}{2}}}$para un entero k ). Las aristas dirigidas del grafo se definen mediante los 3 vectores (1,1), (1,0) y (1,-1): Para cada vértice, si la suma de un vector conduce a otro vértice y el segmento de línea que lo conecta se encuentra dentro del diamante azteca, existe una arista dirigida correspondiente. Definimos las fuentes como los vértices de coordenada y negativa en las aristas izquierdas del diamante azteca, y los sumideros como los vértices de coordenada y negativa en las aristas derechas del diamante azteca. Luego, un teselado define una tupla de caminos sin intersección comenzando en cada fuente y aplicando repetidamente las siguientes reglas:

• elige (1,1) en el vértice inferior izquierdo de una casilla vertical,
• elige dos veces (1,0) en el vértice izquierdo de una casilla horizontal,
• elige (1,-1) en un vértice superior izquierdo de una casilla vertical.

Estos movimientos son similares a los caminos de Schröder . Por ejemplo, consideremos un diamante azteca de orden 2, y después de dibujar su grafo dirigido podemos etiquetar sus fuentes.${\displaystyle a_{a},a_{2}}$y sus fregaderos${\displaystyle b_{1},b_{2}}$En su grafo dirigido, podemos contar los caminos dirigidos desde${\displaystyle a_{i}}$a${\displaystyle b_{j}}$para cada par${\displaystyle (i,j)\in \{1,2\}\times \{1,2\}}$. Llamar${\displaystyle C_{i,j}}$el resultado de cada conteo. Esto nos da una matriz,

${\displaystyle P_{2}={\begin{bmatrix}C_{1,1}&C_{1,2}\\C_{2,1}&C_{2,2}\\\end{bmatrix}}={\begin{bmatrix}6&2\\2&2\\\end{bmatrix}}.}$

Entonces, por el lema de Lindström-Gessel-Viennot ^{[ 5 ]} , el número de caminos que no se intersecan para orden 2 es

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

lo mismo que el número de teselaciones de dominó. Más generalmente, det${\displaystyle (P_{n})=}$número de caminos que no se cruzan desde las fuentes hasta los sumideros.

Eu y Fu demostraron que los caminos de Schröder y los recubrimientos del diamante azteca están en biyección . ^{[ 6 ]} Por lo tanto, encontrar el determinante de la matriz de caminos${\displaystyle P_{n}}$nos dará el número de teselaciones para el diamante azteca de orden 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 ]} El cálculo del 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${\displaystyle \{1,1,3,11,45,\cdots \}=\{y_{0},y_{1},y_{2},y_{3},y_{4},\cdots \}}$y los grandes números de Schröder son${\displaystyle \{1,2,6,22,90,\cdots \}=\{x_{0},x_{1},x_{2},x_{3},x_{4},\cdots \}}$y, en general, nuestras dos matrices de Hankel serán

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

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

Definir${\displaystyle c(s_{i})\subset D}$ser el conjunto de dominós que cubren el cuadrado${\displaystyle s_{i}}$y dejar${\displaystyle x_{i}}$ser una variable indicadora tal que${\displaystyle x_{i}=1}$si el${\displaystyle i^{th}}$Se utiliza dominó en el recubrimiento, y 0 en los demás casos. Con estas definiciones, la tarea de recubrir el diamante azteca puede reducirse a un problema de satisfacción de restricciones formulado como un programa entero binario:

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

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

El${\displaystyle i^{th}}$La restricción garantiza que el cuadrado${\displaystyle s_{i}}$estará cubierto por una sola baldosa, y la colección de${\displaystyle m}$Las restricciones garantizan que cada casilla quede cubierta (sin huecos). Esta formulación se puede resolver con programas estándar de programación entera . Se pueden añadir restricciones para forzar la colocación de fichas específicas, asegurar un número mínimo de fichas horizontales o verticales, o generar mosaicos distintos.

Un enfoque alternativo consiste en aplicar el algoritmo X de Knuth para enumerar los recubrimientos válidos para el problema.

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