Diamante azteca

En combinatoria de particiones , el rombo azteca (o diamante azteca ) de orden es una figura formada por celdas inducidas por una red entera plana , cuyos centros (puntos con coordenadas semienteras ) satisfacen la desigualdad . $norte$ ${\ estilo de visualización | x | + | y | \ leq n}$

Estas figuras se estudian en relación con las propiedades del conjunto de sus teselas de dominó (teselas de celdas). ${\ estilo de visualización 1 \ veces 2}$

Historia

El diamante azteca fue mencionado por primera vez en el trabajo de Elkis , Kuperberg, Larsen y Propp [1] [2] .

El teorema del círculo polar ártico (ver más abajo) fue probado por W. Jokush, J. Propp y P. Shor en 1995. [3]

Conceptos relacionados

Rango dividido

El rango de división de un diamante azteca en fichas de dominó es el número mínimo de rotaciones de dos fichas de dominó que tienen un borde largo común alrededor del centro de su cara común, necesarias para convertir la división en una en la que todas las fichas queden horizontales (obviamente, solo hay una de esas divisiones). Se puede probar que tal transformación siempre es posible a través de tales transformaciones, de modo que la noción de rango está definida para cualquier partición . [2] $T$ $T$

El rango máximo posible de dividir un diamante azteca de orden se logra con una división en la que todas las fichas están orientadas verticalmente. En este caso, el rango es [4] $norte$ ${\frac{1}{6}}n(n+1)(2n+1)$

Función de altura

Para una división fija arbitraria de un diamante, es conveniente considerar una función de altura. Esta es una función definida en los nodos de un retículo entero ubicado dentro del rombo o en su borde, y tomando valores enteros.

Que se fije alguna división del diamante en fichas de dominó. Consideremos una coloración de tablero de ajedrez de celdas de diamante, en la que la celda superior derecha es negra. En cada uno de los bordes de las celdas pondremos una flecha en tal dirección que la celda blanca quede a la derecha de la flecha, y la negra a la izquierda. Denotemos el punto como . Considere cualquier camino que pase exclusivamente a lo largo de los límites de las fichas de dominó que rompen el diamante. Entonces, para un punto de red , la función de altura será igual a la diferencia en el número de flechas en este camino, que se encuentran, respectivamente, codirigidas e inversamente dirigidas a este camino. [2] [5] ${\ estilo de visualización (-n; 0)}$ $v_{0}$ $v_{0}$ $v$ $v$ $H(v)$

En diferentes fuentes, la definición de una función puede diferir por una constante, pero para las aplicaciones esto no es esencial.

Esta definición resulta ser independiente de la elección de la ruta, pero depende solo de la partición.

La notación estándar para mosaicos en una división es

Para simplificar las ilustraciones y formular pruebas, a menudo se usa una división condicional de todas las teselas de una teselación particular bajo consideración en cuatro clases . [6] [7] Para describirlos, es conveniente imaginar la coloración de las celdas del diamante azteca como un tablero de ajedrez, de modo que la parte superior de las dos celdas más a la izquierda es negra. Entonces las clases se definen así: ${\ estilo de visualización 1 \ veces 2}$

N (norte - norte) - mosaico orientado horizontalmente, en el que la celda izquierda es negra;
S (sur - sur): un mosaico orientado horizontalmente, en el que la celda izquierda es blanca;
W (oeste - oeste): un mosaico orientado verticalmente, en el que la celda superior es negra;
E (este - este): un mosaico orientado verticalmente, en el que la celda superior es blanca.

Los nombres de las clases parecen corresponder a los lados en los que se ubican las celdas en dos particiones triviales (donde cada horizontal o vertical es una línea recta de mosaicos sucesivos). Al ilustrar un diamante, los mosaicos de diferentes clases a veces se representan en diferentes colores.

Teorema sobre el número de particiones

La primera cuestión que se planteó la ciencia con respecto al diamante azteca fue el número de posibles divisiones de esta figura en fichas de dominó.

El siguiente teorema se puede probar de muchas maneras utilizando varios métodos y construcciones matemáticas, en particular, condensación de Dodgson, matrices alternas, coincidencias perfectas ponderadas o números y caminos de Schroeder (las cuatro herramientas se refieren a diferentes pruebas posibles).

Hay formas exactas de dividir el diamante azteca del orden en mosaicos del tamaño de celdas, cuyas esquinas se encuentran en los nodos de la red de enteros. ${\ estilo de visualización 2 ^ {\ frac {n (n + 1)} {2}}}$ $norte$ ${\ estilo de visualización 1 \ veces 2}$

A continuación indicaremos el número de dichas particiones por (del inglés "diamante azteca") $AD(n)$

Prueba en términos de matrices alternas

Al probar mediante matrices alternas , a una partición arbitraria de un rombo azteca de orden se le asigna una matriz de tamaño , cuyos elementos corresponden a puntos enteros comparables en módulo 2 y que se encuentran dentro del rombo (cada diagonal se percibe como una fila o columna de la matriz). Si tal punto pertenece a los límites de dos fichas de dominó, entonces el elemento de matriz correspondiente se toma igual a -1, si es tres, entonces 0, si es cuatro, entonces 1. $norte$ $n\veces n$

Se puede probar que las matrices definidas de esta forma siempre serán de signo alternado. Además, se puede demostrar que una matriz particular se puede obtener exactamente a partir de particiones, donde es el número de unos en la matriz . $A$ ${\ estilo de visualización 2^{N_{+}(A)))$ ${\ estilo de visualización {N_ {+} (A)))$ $A$

De manera similar, considerando puntos enteros que son incomparables módulo 2, que se encuentran dentro de la figura y en el límite, y las matrices correspondientes de tamaño , podemos probar que cualquier matriz de este tipo corresponde a particiones, donde es el número de menos unos en la matriz . ${\ estilo de visualización (n + 1) \ veces (n + 1)}$ ${\ estilo de visualización 2^{N_{-}(A)))$ ${\ estilo de visualización {N_ {-} (A)))$ $A$

Como resultado, a partir de la identidad obvia para las matrices de tamaño con alternancia de signos y la identidad resultante ( donde es el conjunto de todas las matrices de orden con alternancia de signos ) resulta fácilmente que [8] $n\veces n$ $N_{+}(A)=N_{-}(A)+n$ $AD(n)=\sum \limits _{A\in {\mathcal {M}}_{n+1}}{2^{N_{-}(A)))=\sum \limits _ {A\en {\mathcal {M}}_{n}}{2^{N_{+}(A)))$ ${\mathcal {M}}_{n}$ $norte$

AD(n)=2^{n}\sum \limits _{A\in {\mathcal {M}}_{n}}{2^{N_{-}(A)))=2^ {n}AD(n-1)=2^{n+(n-1)}AD(n-2)=\dots =2^{(1+2+\dots +n)}=2^{\frac {n(n+1)}{2}}

Prueba haciendo coincidir

Al demostrar por correspondencias , consideramos un grafo cuyos vértices corresponden a las celdas del rombo azteca de orden , y las aristas pasan entre los vértices, cuyas celdas son adyacentes horizontal o verticalmente. El número de mosaicos del diamante de orden azteca es igual al número de combinaciones perfectas en el gráfico . $G_{n}$ $norte$ $norte$ $GRAMO$

En la demostración de un grafo arbitrario y una función de peso en sus aristas , se considera su suma estadística , donde la suma bajo el signo de suma se realiza sobre todos los emparejamientos perfectos posibles. $G=(V,E)$ $\omega :E\to {\mathbb {R} }$ $Z(G)=\sum \limits _{M}\prod \limits _{e\in M}\omega (e)$

La base de la prueba es un lema que permite cortar cuatro vértices de un gráfico, reorganizar los bordes y los pesos junto a ellos de la manera correcta, de modo que la función de partición del gráfico cambie en una cantidad predecible. Esto solo es posible si los vértices que se eliminarán tienen una configuración de borde especial con otros cuatro vértices. Para lograr la existencia de un gran número de tales configuraciones en el grafo en consideración, el grafo puede extenderse a algún grafo triplicando correctamente los vértices para que el número de coincidencias no cambie. $G_{n}$ ${\ Displaystyle {\ tilde {G_{n}}}}$

Se supone que los pesos de los bordes del gráfico son iguales a uno (entonces el número de coincidencias es igual a la función de partición), así como los pesos del gráfico , y los pesos no triviales aparecen solo después de aplicar la eliminación de vértices. lema Sin embargo, en el gráfico obtenido después de todas las eliminaciones posibles de vértices , todos los pesos en los bordes son iguales a o , y los bordes con peso se incluyen necesariamente en cualquier coincidencia. Además, tras descartar las aristas, el peso resulta ser igual al gráfico del rombo azteca del orden anterior, solo que con el peso de cada arista reducido a la mitad (y exactamente sus aristas participan en cada emparejamiento). Esto nos permite derivar la fórmula recursiva : [9] $G_{n}$ ${\ Displaystyle {\ tilde {G_{n}}}}$ ${\tilde {G_{n}}}^{*}$ $una$ ${\frac{1}{2))$ $una$ ${\tilde {G_{n}}}^{*}$ $una$ ${\ Displaystyle G_ {n-1}}$ ${\ estilo de visualización n (n-1)}$

AD(n)=Z(G_{n})=Z({\tilde {G_{n))})=2^{n^{2))Z({\tilde {G_{n)) }^{*})=2^{n^{2}}{\frac {Z(G_{n-1})}{2^{n(n-1)}}}=2^{n}Z (G_{n-1})=2^{n}AD(n-1)

Prueba en términos de números de Schroeder

Otra forma de probarlo es asignar a cada partición del diamante de orden azteca un conjunto de caminos de Schroeder disjuntos uno a uno . Entonces, el número de particiones posibles resulta ser igual al número de dichos conjuntos. $norte$ $norte$

Para hacer esto, basta con marcar el medio de los segmentos verticales de la parte inferior izquierda del borde del diamante y luego dibujar líneas desde ellos, dibujando cada vez un nuevo segmento simétricamente en relación con el centro del dominó, en el que el se ubica el segmento: horizontalmente para mosaicos horizontales y en ángulo para mosaicos verticales. Entonces, si continuamos cada camino fuera del diamante con líneas inclinadas al mismo nivel, entonces obtenemos solo caminos de Schroeder que no se cruzan (se garantiza que cada camino a lo largo del diamante termine en la misma línea horizontal donde comenzó). $norte$

Además, el número de tales conjuntos resulta ser igual al determinante de la matriz de Hankel compuesta por números de Schroeder . Considerando pequeños caminos de Schroeder (es decir, aquellos en los que los segmentos horizontales no se encuentran en el nivel 0) y el número de sus conjuntos sin intersecciones (también será expresado por la matriz de Hankel, pero para una secuencia diferente), podemos derivar el relaciones y , de donde es fácil obtener una expresión recursiva para [ 10] : $H_n$ $G_{n}$ $H_{n}=G_{n+1}$ $H_{n}=2^{n}G_{n}$ $H_n$

AD(n)=H_{n}=2^{n}H_{n-1}=2^{n}AD(n-1)

Prueba moviendo una cadena de fichas de dominó que se cruzan

En esta prueba, primero se convierte un diamante azteca en una nueva figura recortando cuatro celdas. Además, las celdas cortadas cumplen las siguientes condiciones:

en la coloración del ajedrez, dos de ellos son blancos y dos negros;
cuando se recortan celdas blancas y negras, los mosaicos de celdas cerca de la mitad del límite se determinan de manera única, de modo que la parte restante es un diamante azteca de orden ; $n-1$
al cortar cuatro celdas, la orientación de todas las fichas de dominó que tocan el borde se determina de manera única, de modo que la parte restante es un diamante azteca de orden . $n-2$

Considerando un par arbitrario de particiones del propio diamante y una figura con cuatro celdas recortadas, se puede distinguir una cadena de fichas de dominó que se cruzan y van de una celda a otra (las fichas de dominó de una y otra partición se alternan, dos fichas de dominó adyacentes cualesquiera se cruzan en una celda ). Luego, intercambiando partes de esta cadena de una partición a otra, se pueden obtener particiones de dos figuras, cada una de las cuales tiene solo dos celdas recortadas. Esto da la relación de recurrencia [4]

AD(n)AD(n-2)=2AD(n-1)^{2}

Usando el mismo método, puede derivar una fórmula corta para un caso particular de la función generadora (ver más abajo):

AD(n;x)=(1+x)^{\frac {n(n+1)}{2))

Función generadora de particiones

Denotemos el rango de la división , y - la mitad del número de mosaicos verticales en esta división (el número de mosaicos verticales siempre es par, ya que cualquier línea horizontal entera divide el diamante en dos partes con un número par de celdas en cada una - que significa que cada una de esas líneas horizontales está atravesada por un número par de mosaicos verticales). ${\ estilo de visualización r (T)}$ $T$ ${\ estilo de visualización v (T)}$

En el trabajo de Elkis , Kuperberg, Larsen y Propp se consideró una función generadora , donde la sumatoria se realiza sobre todas las posibles particiones del diamante azteca de orden . En el trabajo se encontró que . $AD(n;x,q)=\sum \limits _{T}x^{v(T)}q^{r(T)}$ $T$ $norte$ $AD(n;x,q)=\prod \limits _{k=0}^{n-1}{{(1+xq^{2k+1})}^{nk))$

En particular, la fórmula habitual para el número de particiones se deriva de esta identidad: $AD(n;1,1)=\prod \limits _{k=0}^{n-1}2^{nk}=2^{\frac {n(n+1)}{2} }$

Divisiones aleatorias

Algoritmo para generar una partición aleatoria

Existe un algoritmo bien conocido para la elección equiprobable de una división aleatoria de un diamante de un tamaño dado de todas las divisiones de dicho tamaño. [6] [11]

Para generar una división de tamaño aleatorio, el algoritmo utiliza una división de diamante azteca de tamaño aleatorio pregenerada y la transforma de una manera especial con aleatoriedad adicional. Por lo tanto, para generar una división de tamaño aleatoria, debe generar divisiones de tamaño de manera consistente . $norte$ $n-1$ $norte$ ${\ estilo de visualización 1,2, \ puntos, n-1, n}$

La transformación en la transición de tamaño a incluye tres etapas: $n-1$ $norte$

Destrucción. Los siguientes pares de fichas (si los hay) se eliminan de la división:
- la teja S, que está en contacto con la cara inferior de la celda tipo N;
- teja E, que está en contacto con el lado derecho de la teja tipo W.
Cambio. Todas las fichas restantes se desplazan una celda según su tipo en notación estándar: N arriba, S abajo, E a la derecha, W a la izquierda. La etapa anterior de destrucción asegura que no habrá superposición de una ficha sobre otra.
Generación. Se demuestra que como resultado de las dos etapas anteriores, todas las celdas vacías en el área del tamaño del diamante azteca se pueden dividir en cuadrados de 2x2. En la etapa de generación, cada uno de esos cuadrados se llena por separado con dos mosaicos verticales o dos horizontales con la misma probabilidad. $norte$

El teorema del círculo polar ártico

Considere un círculo inscrito en un cuadrado que delimita un diamante azteca. Corta cuatro esquinas del cuadrado. Resulta que para un mosaico elegido al azar, con una probabilidad muy alta, casi todas las fichas de dominó que caen en estas esquinas, es decir, fuera de este círculo, estarán "congeladas": en las esquinas inferior y superior estarán todas horizontales, y en las esquinas izquierda y derecha serán verticales. Por el contrario, el comportamiento del mosaico dentro de este círculo no se puede predecir, es caótico. Todo lo anterior constituye el enunciado del Teorema del Círculo Polar Ártico, probado en 1995 por W. Jokush, J. Propp y P. Shor [12] [3] :

Sea la probabilidad de que, con una coloración aleatoria de un rombo de orden , todas las fichas fuera del círculo ampliado una vez inscrito en este rombo se ubiquen de manera determinista, es decir, en el borde superior todas las celdas serán de clase N, en la parte inferior - de la clase S, a la derecha - de la clase W, a la izquierda - de la clase E. $p_{n,\varepsilon}$ $norte$ $1+\varepsilon$

Luego, para cualquier retención de . $\varepsilon >0$ $p_{n,\varepsilon}\a 1$ $n\to\infty$

De hecho, el teorema establece que en particiones aleatorias de diamantes suficientemente grandes, casi toda la región fuera del círculo inscrito se llenará exactamente, como particiones triviales.

Notas

↑ Smirnov, 2015 , pág. 5.
↑ 1 2 3 Noam Elkies, Greg Kuperberg, Michael Larsen, James Propp. Matrices de signos alternos y mosaicos de dominó // arXiv:math/9201305. - 1991-05-31. Archivado desde el original el 25 de marzo de 2018.
↑ 1 2 William Jockusch, James Propp, Peter Shor. Mosaicos aleatorios de dominó y el teorema del círculo polar ártico // arXiv:math/9801068. - 1998-01-13. Archivado desde el original el 25 de septiembre de 2017.
↑ 1 2 Kokhas, 2008 .
↑ Smirnov, 2015 .
↑ 1 2 ", Eric Nordenstam, "", vol. 15 (2010), Papel núm. 3, páginas. Sobre el algoritmo de barajado para mosaicos de dominó // Diario electrónico de probabilidad. - 2010. - Vol. 15.- Pág. 75-95. Archivado desde el original el 25 de marzo de 2018.
↑ Para escolares. 013. Small ShAD - Problemas asintóticos de combinatoria - Victor Kleptsyn . YouTube (22 de abril de 2015). Recuperado: 24 de marzo de 2018. (indefinido)
↑ Smirnov, 2015 , pág. 7-24.
↑ Smirnov, 2015 , pág. 25-32.
↑ Smirnov, 2015 , pág. 33-42.
↑ Eric Nordenstam. Sobre el algoritmo de barajado para mosaicos de dominó // arXiv:0802.2592 [matemáticas]. — 2008-02-19. Archivado desde el original el 25 de marzo de 2018.
↑ Smirnov, 2015 , pág. 46.

Literatura

Smirnov, E.Yu. Tres puntos de vista sobre el diamante azteca . — M .: MTsNMO , 2015. — 48 p. - ISBN 978-5-4439-0279-1 .
K. Kokhas. Partiendo diamantes y cuadrados aztecas en fichas de dominó // Apuntes de Seminarios Científicos POMI. - 2008. - T. 360 . - S. 180-230 .

Enlaces

Burkard Polster. El TEOREMA DEL CÍRCULO ÁRTICO o ¿Por qué los físicos juegan al dominó? . Matólogo . Vídeo de YouTube (24-12-2020). Recuperado: 28 de diciembre de 2020. (indefinido)