Diamant aztec

În combinatoria partițiilor , diamantul aztec (sau diamantul aztec ) de ordin este o figură constând din celule induse de o rețea întregă plată , ale cărei centre (puncte cu coordonate pe jumătate întreg ) satisfac inegalitatea . $n$ $|x|+|y|\leq n$

Aceste figuri sunt studiate în legătură cu proprietățile setului de plăci de domino (placuri de celule). $1\times 2$

Istorie

Diamantul aztec a fost menționat pentru prima dată în lucrarea lui Elkis , Kuperberg, Larsen și Propp [1] [2] .

Teorema Cercului Arctic (vezi mai jos) a fost demonstrată de W. Jokush, J. Propp și P. Shor în 1995. [3]

Concepte înrudite

Rang împărțit

Gradul de împărțire a unui diamant aztec în piese de domino este numărul minim de rotații a două piese de domino care au o margine lungă comună în jurul centrului feței lor comune, necesar pentru a transforma despărțirea într-una în care toate plăcile se află orizontal (există evident doar o astfel de scindare). Se poate dovedi că o astfel de transformare este întotdeauna posibilă prin astfel de transformări, astfel încât noțiunea de rang este definită pentru orice partiție . [2] $T$ $T$

Rangul maxim posibil de împărțire a unui diamant aztec de ordin se realizează cu o scindare în care toate plăcile sunt orientate vertical. În acest caz, rangul este [4] $n$ ${\frac {1}{6}}n(n+1)(2n+1)$

Funcția de înălțime

Pentru o diviziune fixă arbitrară a unui diamant, este convenabil să se ia în considerare o funcție de înălțime. Aceasta este o funcție definită pe nodurile unei rețele întregi situate în interiorul diamantului sau pe marginea acestuia și luând valori întregi.

Să se rezolve o oarecare diviziune a diamantului în plăci de domino. Să luăm în considerare o colorare în șah a celulelor de diamant, în care celula din dreapta sus este neagră. Pe fiecare dintre marginile celulelor, vom pune o săgeată în așa direcție încât celula albă să fie în dreapta săgeții, iar cea neagră să fie la stânga. Să notăm punctul ca . Luați în considerare orice cale de la până la trecerea exclusiv de-a lungul granițelor plăcilor de domino care rup diamantul. Apoi, pentru un punct de rețea , funcția de înălțime va fi egală cu diferența dintre numărul de săgeți de pe această cale, situate, respectiv, co-direcționate și invers direcționate către această cale. [2] [5] $(-n;0)$ $v_{0}$ $v_{0}$ $v$ $v$ $H(v)$

În diferite surse, definiția unei funcții poate diferi printr-o constantă, dar pentru aplicații acest lucru nu este esențial.

Această definiție se dovedește a fi independentă de alegerea căii, dar depinde doar de partiție.

Notația standard pentru plăci într-o împărțire este

Pentru a simplifica ilustrațiile și a formula dovezi, este adesea folosită o împărțire condiționată a tuturor plăcilor dintr- o anumită placă luată în considerare în patru clase . [6] [7] Pentru a le descrie, este convenabil să ne imaginăm colorarea celulelor diamantului aztec ca pe o tablă de șah, astfel încât partea de sus a celor două celule din stânga să fie neagră. Apoi clasele sunt definite astfel: $1\times 2$

N (nord - nord) - țiglă orientată orizontal, în care celula din stânga este neagră;
S (sud - sud) - o țiglă orientată orizontal, în care celula din stânga este albă;
W (vest - vest) - o țiglă orientată vertical, în care celula de sus este neagră;
E (est - est) - o țiglă orientată vertical, în care celula de sus este albă.

Numele claselor par să corespundă laturilor în care celulele sunt situate în două partiții banale (unde fiecare orizontală sau verticală este o linie dreaptă de plăci succesive). Când ilustrăm un diamant, plăcile de diferite clase sunt uneori descrise în culori diferite.

Teorema privind numărul de partiții

Prima întrebare pe care știința a luat-o în considerare cu privire la diamantul aztec a fost numărul posibilelor diviziuni ale acestei figuri în plăci de domino.

Următoarea teoremă poate fi demonstrată în mai multe moduri folosind diferite metode și construcții matematice - în special, condensarea Dodgson, matrice alternantă, potriviri perfecte ponderate sau numere și căi Schroeder (toate cele patru instrumente se referă la diferite dovezi posibile).

Există exact modalități de a sparge diamantul aztec de ordine în plăci de dimensiunea celulelor, ale căror colțuri se află la nodurile rețelei întregi. $2^{\frac {n(n+1)}{2))$ $n$ $1\times 2$

Mai jos vom nota numărul de astfel de partiții cu (din engleză „diamond aztec”) $AD(n)$

Dovada din punct de vedere al matricilor alternante

Atunci când se demonstrează prin matrici alternante , unei partiții arbitrare a unui diamant aztec de ordin i se atribuie o matrice de dimensiune , ale cărei elemente corespund unor puncte întregi comparabile în modulo 2 și aflate în interiorul diamantului (fiecare diagonală este percepută ca un rând sau coloană). a matricei). Dacă un astfel de punct aparține granițelor a două piese de domino, atunci elementul matricei corespunzător este luat egal cu -1, dacă trei, atunci 0, dacă patru, atunci 1. $n$ $n\ ori n$

Se poate dovedi că matricele astfel definite vor fi întotdeauna alternante de semne. Mai mult, se poate dovedi că o anumită matrice poate fi obținută exact din partiții, unde este numărul de unități din matrice . $A$ ${\displaystyle 2^{N_{+}(A)))$ ${\displaystyle {N_{+}(A)))$ $A$

În mod similar, luând în considerare puncte întregi care sunt incomparabile modulo 2, aflate în interiorul figurii și pe graniță, și matricele corespunzătoare de dimensiune , putem demonstra că orice astfel de matrice corespunde partițiilor, unde este numărul de unități minus din matrice . $(n+1)\times (n+1)$ ${\displaystyle 2^{N_{-}(A)))$ ${\displaystyle {N_{-}(A)))$ $A$

Ca urmare, din identitatea evidentă pentru matricele de mărime alternante de semne și identitatea rezultată ( unde este mulțimea tuturor matricelor de ordine alternante de semne ) rezultă cu ușurință că [8] $n\ ori n$ $N_{+}(A)=N_{-}(A)+n$ $AD(n)=\sum \limits _{A\in {\mathcal {M}}_{n+1}}{2^{N_{-}(A)))=\sum \limits _ {A\în {\mathcal {M}}_{n}}{2^{N_{+}(A)))$ ${\mathcal {M}}_{n}$ $n$

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}}

Dovada prin potrivire

Când demonstrăm prin potriviri , luăm în considerare un grafic ale cărui vârfuri corespund celulelor diamantului aztec de ordin , iar muchiile trec între vârfuri, ale căror celule sunt adiacente orizontal sau vertical. Numărul de plăci ale diamantului aztec de ordine este egal cu numărul de potriviri perfecte din grafic . $G_{n}$ $n$ $n$ $G$

În demonstrația pentru un grafic arbitrar și o funcție de greutate pe muchiile sale, se ia în considerare suma sa statistică , unde însumarea sub semnul sumei este efectuată peste toate potrivirile perfecte posibile. $G=(V,E)$ $\omega:E\to {\mathbb {R} }$ $Z(G)=\sum\limits _{M}\prod \limits _{e\in M}\omega (e)$

Baza demonstrației este o lemă care permite tăierea a patru vârfuri dintr-un grafic, rearanjarea muchiilor și greutăților de lângă ele în mod corect, astfel încât funcția de partiție a graficului să se modifice într-o cantitate previzibilă. Acest lucru este posibil numai dacă vârfurile care trebuie eliminate sunt într-o configurație specială de margine cu alte patru vârfuri. Pentru a realiza existența unui număr mare de astfel de configurații în graficul luat în considerare, graficul poate fi extins la un anumit grafic prin triplarea corectă a vârfurilor, astfel încât numărul de potriviri să nu se modifice. $G_{n}$ ${\tilde {G_{n}})$

Se presupune că greutățile muchiilor graficului sunt egale cu unu (atunci numărul de potriviri este egal cu funcția de partiție), precum și greutățile graficului , iar greutățile netriviale apar numai după aplicarea eliminării vârfurilor lema. Totuși, în graficul obținut după toate ștergerile posibile ale vârfurilor , toate ponderile de pe muchii sunt egale fie cu , fie cu , iar muchiile cu greutate sunt în mod necesar incluse în orice potrivire. În plus, după aruncarea marginilor, greutatea se dovedește a fi egală cu graficul diamant aztec din ordinul precedent, doar cu greutatea fiecărei margini redusă la jumătate (și exact marginile sale participă la fiecare potrivire). Acest lucru ne permite să derivăm formula recursivă : [9] $G_{n}$ ${\tilde {G_{n}})$ ${\tilde {G_{n}}}^{*}$ $unu$ ${\frac {1}{2))$ $unu$ ${\tilde {G_{n}}}^{*}$ $unu$ $G_{n-1)$ $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)

Dovada în termeni de numere Schroeder

O altă modalitate de a demonstra acest lucru este să atribui fiecărei partiții a diamantului aztec de ordin un set de căi Schroeder disjunse unu-la-unu . Apoi, numărul de partiții posibile se dovedește a fi egal cu numărul de astfel de seturi. $n$ $n$

Pentru a face acest lucru, este suficient să marcați mijlocul segmentelor verticale din partea stângă inferioară a marginii diamantului și apoi să trageți linii din ele, de fiecare dată desenând un nou segment simetric față de centrul dominoului, în care segmentul este amplasat - orizontal pentru plăci întinse orizontal și în unghi pentru plăci verticale. Apoi, dacă continuăm fiecare cale în afara diamantului cu linii înclinate la același nivel, atunci obținem doar căi Schroeder care nu se intersectează (fiecare drum de-a lungul diamantului este garantat să se termine pe aceeași linie orizontală de unde a început). $n$

Mai mult, numărul de astfel de mulțimi se dovedește a fi egal cu determinantul matricei Hankel compusă din numere Schroeder . Luând în considerare traseele Schroeder mici (adică acelea în care segmentele orizontale nu se află la nivelul 0) și numărul mulțimilor lor fără intersecții (va fi exprimat și prin matricea Hankel, dar pentru o secvență diferită), putem deriva relații și , din care se obține ușor o expresie recursivă pentru [ 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)

Dovada prin deplasarea unui lanț de piese de domino care se intersectează

În această dovadă, un diamant aztec este mai întâi transformat într-o nouă figură prin tăierea a patru celule. În plus, celulele tăiate îndeplinesc următoarele condiții:

în colorarea șahului, două dintre ele sunt albe și două sunt negre;
la tăierea oricăror celule alb-negru, plăcile celulelor de lângă jumătatea limitei sunt determinate în mod unic, astfel încât partea rămasă este un diamant aztec de ordine ; $n-1$
la tăierea a patru celule, orientarea tuturor pieselor de domino care ating granița este determinată în mod unic, astfel încât partea rămasă este un diamant aztec de ordine . $n-2$

Luând în considerare o pereche arbitrară de partiții ale diamantului însuși și o figură cu patru celule decupate, se poate distinge un lanț de domino care se intersectează care merg de la o celulă la alta (dominourile de la una și alta partiție alternează, oricare două dominos adiacente se intersectează într-o celulă). ). Apoi, schimbând părți ale acestui lanț dintr-o partiție și din alta, se pot obține partiții cu două figuri, fiecare având doar două celule decupate. Aceasta dă relația de recurență [4]

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

Folosind aceeași metodă, puteți obține o formulă scurtă pentru un anumit caz al funcției de generare (vezi mai jos):

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

Funcția de generare a partițiilor

Să notăm rangul împărțirii și - jumătate din numărul de plăci verticale din această împărțire (numărul de plăci verticale este întotdeauna par, deoarece orice linie orizontală întreagă împarte diamantul în două părți cu un număr par de celule în fiecare - care înseamnă că fiecare astfel de linie orizontală este traversată de un număr par de plăci verticale) . $r(T)$ $T$ $v(T)$

În lucrarea lui Elkis , Kuperberg, Larsen și Propp, a fost luată în considerare o funcție generatoare , în care însumarea este efectuată pe toate partițiile posibile ale diamantului aztec de ordine . S-a constatat în lucrare că . $AD(n;x,q)=\sum \limits _{T}x^{v(T)}q^{r(T)}$ $T$ $n$ $AD(n;x,q)=\prod \limits _{k=0}^{n-1}{{(1+xq^{2k+1})}^{nk))$

În special, formula obișnuită pentru numărul de partiții rezultă din această identitate: $AD(n;1,1)=\prod \limits _{k=0}^{n-1}2^{nk}=2^{\frac {n(n+1)}{2} }$

Divizări aleatorii

Algoritm pentru generarea unei partiții aleatoare

Există un algoritm binecunoscut pentru alegerea echiprobabilă a divizării aleatorii a unui diamant de o dimensiune dată din toate diviziunile de o astfel de dimensiune. [6] [11]

Pentru a genera o împărțire aleatorie de dimensiune, algoritmul folosește o divizare aleatorie de diamant aztecă pre-generată și o transformă într-un mod special, cu caracter aleatoriu suplimentar. Astfel, pentru a genera o împărțire aleatoare a dimensiunii, trebuie să generați în mod constant divizări de dimensiune . $n$ $n-1$ $n$ $1,2,\dots ,n-1,n$

Transformarea în tranziția de la dimensiune la include trei etape: $n-1$ $n$

Distrugere. Următoarele perechi de plăci (dacă există) sunt îndepărtate din împărțire:
- țigla S, care este în contact cu fața inferioară a celulei de tip N;
- țigla E, care este în contact cu partea dreaptă a țiglei de tip W.
Schimb. Toate plăcile rămase sunt deplasate cu o celulă în funcție de tipul lor în notație standard - N sus, S în jos, E dreapta, W stânga. Etapa anterioară de distrugere asigură că nu va exista suprapunere a unei plăci pe alta.
Generaţie. Se dovedește că, în urma celor două etape anterioare, toate celulele goale din zona mărimii diamantului aztec pot fi împărțite în pătrate 2x2. În etapa de generare, fiecare astfel de pătrat este umplut separat cu două plăci verticale sau două orizontale, cu probabilitate egală. $n$

Teorema Cercului Arctic

Luați în considerare un cerc înscris într-un pătrat care mărginește un diamant aztec. Ea taie patru colțuri ale pătratului. Se dovedește că, pentru o placă aleasă aleatoriu, cu o probabilitate foarte mare, aproape toate piesele de domino care cad în aceste colțuri, adică în afara acestui cerc, vor fi „înghețate”: în colțurile de jos și de sus vor fi toate orizontale și in colturile stanga si dreapta vor fi verticale . Dimpotrivă, comportamentul placajului în interiorul acestui cerc nu poate fi prezis - este haotic. Toate cele de mai sus constituie afirmația Teoremei Cercului Arctic, demonstrată în 1995 de W. Jokush, J. Propp și P. Shor [12] [3] :

Să fie probabilitatea ca, cu o colorare aleatorie a unui diamant de ordin , toate plăcile din afara cercului mărit odată înscrise în acest diamant să fie situate într-un mod determinist, adică pe marginea superioară toate celulele să fie din clasa N, în jos - din clasa S, în dreapta - din clasa W, în stânga - din clasa E. $p_{n,\varepsilon }$ $n$ $1+\varepsilon$

Apoi, pentru orice reținere pentru . $\varepsilon >0$ $p_{n,\varepsilon }\la 1$ $n\la\infty$

De fapt, teorema afirmă că în partițiile aleatorii ale diamantelor suficient de mari, aproape întreaga regiune din afara cercului înscris va fi umplută exact, ca și partițiile triviale.

Note

↑ Smirnov, 2015 , p. 5.
↑ 1 2 3 Noam Elkies, Greg Kuperberg, Michael Larsen, James Propp. Matrici de semne alternante și piese de domino // arXiv:math/9201305. — 31-05-1991. Arhivat din original pe 25 martie 2018.
↑ 1 2 William Jockusch, James Propp, Peter Shor. Piese aleatorii de domino și teorema cercului polar // arXiv:math/9801068. - 13-01-1998. Arhivat din original pe 25 septembrie 2017.
↑ 1 2 Kokhas, 2008 .
↑ Smirnov, 2015 .
↑ 1 2 "", Eric Nordenstam, "", Vol. 15 (2010), Lucrarea nr. 3, paginile. Despre algoritmul de amestecare pentru plăci de domino // Jurnal electronic de probabilitate. - 2010. - Vol. 15. - P. 75-95. Arhivat din original pe 25 martie 2018.
↑ Pentru școlari. 013. Small ShAD - Probleme asimptotice de combinatorie - Victor Kleptsyn . YouTube (22 aprilie 2015). Preluat: 24 martie 2018. (nedefinit)
↑ Smirnov, 2015 , p. 7-24.
↑ Smirnov, 2015 , p. 25-32.
↑ Smirnov, 2015 , p. 33-42.
↑ Eric Nordenstam. Despre algoritmul de amestecare pentru plăci de domino // arXiv:0802.2592 [matematică]. — 19-02-2008. Arhivat din original pe 25 martie 2018.
↑ Smirnov, 2015 , p. 46.

Literatură

Smirnov, E.Yu. Trei vederi asupra diamantului aztec . — M .: MTsNMO , 2015. — 48 p. - ISBN 978-5-4439-0279-1 .
K. Kokhas. Împărțirea diamantelor și pătratelor aztece în piese de domino // Note ale seminariilor științifice POMI. - 2008. - T. 360 . - S. 180-230 .

Link -uri

Burkard Polster. Teorema cercului arctic sau de ce fizicienii joacă domino? . matolog . Video YouTube (24-12-2020). Preluat: 28 decembrie 2020. (nedefinit)