Aztekisk diamant

I kombinatorik av partitioner är den aztekiska diamanten (eller den aztekiska diamanten ) av ordning en figur som består av celler inducerade av ett platt heltalsgitter , vars centra (punkter med halvheltalskoordinater ) tillfredsställer olikheten . $n$ $|x|+|y|\leq n$

Dessa figurer studeras i samband med egenskaperna hos uppsättningen av deras beläggningar av dominobrickor (beläggningar av celler). $1\times 2$

Historik

Den aztekiska diamanten nämndes först i verk av Elkis , Kuperberg , Larsen och Propp [1] [2] .

Arctic Circle Theorem (se nedan) bevisades av W. Jokush, J. Propp och P. Shor 1995. [3]

Relaterade begrepp

Dela rankning

Rangen för att dela en aztekisk diamant i dominobrickor är det minsta antalet rotationer av två dominobrickor som har en gemensam långkant runt mitten av deras gemensamma yta, vilket är nödvändigt för att göra splittringen till en där alla brickor ligger horisontellt (det finns uppenbarligen bara en sådan uppdelning). Det kan bevisas att en sådan transformation alltid är möjlig genom sådana transformationer, så att begreppet rang definieras för vilken partition som helst . [2] $T$ $T$

Den högsta möjliga rangen för att dela en aztekisk diamant uppnås med en split där alla brickor är orienterade vertikalt. I det här fallet är rangen [4] $n$ ${\frac {1}{6}}n(n+1)(2n+1)$

Höjdfunktion

För en godtycklig fast uppdelning av en diamant är det lämpligt att överväga en funktion av höjden. Detta är en funktion som definieras på noderna i ett heltalsgitter som finns inuti diamanten eller på dess kant, och som tar heltalsvärden.

Låt en del uppdelning av diamanten i dominobrickor fixas. Låt oss överväga en schackbrädefärgning av diamantceller, där den översta cellen längst till höger är svart. På var och en av cellernas gränser kommer vi att sätta en pil i en sådan riktning att den vita cellen är till höger om pilen och den svarta är till vänster. Låt oss beteckna punkten som . Överväg vilken väg som helst från att passera uteslutande längs gränserna för dominobrickorna som bryter diamanten. Sedan, för en gitterpunkt , kommer höjdfunktionen att vara lika med skillnaden i antalet pilar på denna väg, som ligger, respektive, samriktad och omvänt riktad mot denna väg. [2] [5] $(-n;0)$ $v_{0}$ $v_{0}$ $v$ $v$ $H(v)$

I olika källor kan definitionen av en funktion skilja sig med en konstant, men för applikationer är detta inte nödvändigt.

Denna definition visar sig vara oberoende av valet av vägen, men beror bara på partitionen.

Standardnotationen för brickor i en split är

För att förenkla illustrationer och formulera bevis, används ofta en villkorlig uppdelning av alla brickor av en viss platta under övervägande i fyra klasser . [6] [7] För att beskriva dem är det bekvämt att föreställa sig färgningen av cellerna i den aztekiska diamanten som ett schackbräde så att toppen av de två cellerna längst till vänster är svart. Då definieras klasserna så här: $1\times 2$

N (norr - norr) - horisontellt orienterad bricka, där den vänstra cellen är svart;
S (söder - syd) - en horisontellt orienterad bricka, där den vänstra cellen är vit;
W (väst - väst) - en vertikalt orienterad bricka, där den översta cellen är svart;
E (öst - öst) - en vertikalt orienterad platta, där den översta cellen är vit.

Namnen på klasserna verkar motsvara sidorna där cellerna är placerade i två triviala partitioner (där varje horisontell eller vertikal är en rak linje av på varandra följande brickor). När man illustrerar en diamant avbildas ibland brickor av olika klasser i olika färger.

Sats om antalet partitioner

Den första frågan som vetenskapen övervägde om den aztekiska diamanten var antalet möjliga uppdelningar av denna figur i dominobrickor.

Följande teorem kan bevisas på många sätt med hjälp av olika matematiska metoder och konstruktioner - i synnerhet Dodgson-kondensering, alternerande matriser, viktade perfekta matchningar eller Schroeder-tal och -banor (alla dessa fyra verktyg hänvisar till olika möjliga bevis).

Det finns exakta sätt att bryta den aztekiska ordningens diamant i brickor av storleken på celler, vars hörn ligger vid noderna av heltalsgittret. $2^{\frac {n(n+1)}{2))$ $n$ $1\times 2$

Nedan kommer vi att beteckna antalet sådana partitioner med (från engelskan "aztec diamond") $AD(n)$

Bevis i termer av alternerande matriser

När man bevisar genom alternerande matriser , tilldelas en godtycklig partition av en aztekisk diamant av ordning en matris av storlek , vars element motsvarar heltalspunkter jämförbara i modulo 2 och som ligger inuti diamanten (varje diagonal uppfattas som en rad eller kolumn av matrisen). Om en sådan punkt hör till gränserna för två dominobrickor, tas motsvarande matriselement lika med -1, om tre, då 0, om fyra, då 1. $n$ $n\ gånger n$

Det kan bevisas att de matriser som definieras på detta sätt alltid kommer att vara teckenalternerande. Dessutom kan det bevisas att en viss matris kan erhållas exakt från partitioner, där är antalet ettor i matrisen . $A$ ${\displaystyle 2^{N_{+}(A)))$ ${\displaystyle {N_{+}(A)))$ $A$

På samma sätt, med tanke på heltalspunkter som är ojämförliga modulo 2, som ligger innanför figuren och på gränsen, och motsvarande matriser av storlek , kan vi bevisa att varje sådan matris motsvarar partitioner, där är antalet minus ettor i matrisen . $(n+1)\ gånger (n+1)$ ${\displaystyle 2^{N_{-}(A)))$ ${\displaystyle {N_{-}(A)))$ $A$

Som ett resultat, från den uppenbara identiteten för tecken-alternerande matriser av storlek och den resulterande identiteten ( var är mängden av alla tecken-alternerande matriser av ordning ) visar det sig lätt att [8] $n\ gånger n$ $N_{+}(A)=N_{-}(A)+n$ $AD(n)=\summa \limits _{A\in {\mathcal {M}}_{n+1}}{2^{N_{-}(A)))=\summa \limits _ {A\in {\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}}

Bevis genom att matcha

När vi bevisar genom matchningar beaktar vi en graf vars hörn motsvarar cellerna i den aztekiska diamanten av ordning , och kanterna passerar mellan hörnen, vars celler ligger intill horisontellt eller vertikalt. Antalet beläggningar av den aztekiska diamanten av ordning är lika med antalet perfekta matchningar i grafen . $G_{n}$ $n$ $n$ $G$

I beviset för en godtycklig graf och en viktfunktion på dess kanter beaktas dess statistiska summa , där summeringen under summatecknet utförs över alla möjliga perfekta matchningar. $G=(V,E)$ $\omega :E\to {\mathbb {R} }$ $Z(G)=\summa \limits _{M}\prod \limits _{e\in M}\omega (e)$

Grunden för beviset är ett lemma som gör det möjligt att skära ut fyra hörn från en graf, ordna om kanterna och vikterna bredvid dem på rätt sätt, så att grafens partitionsfunktion ändras med en förutsägbar mängd. Detta är endast möjligt om de hörn som ska tas bort är i en speciell kantkonfiguration med ytterligare fyra hörn. För att uppnå förekomsten av ett stort antal sådana konfigurationer i grafen under övervägande, kan grafen utökas till någon graf genom att korrekt tredubbla hörnen så att antalet matchningar inte ändras. $G_{n}$ ${\displaystyle {\tilde {G_{n))))$

Vikterna på grafens kanter antas vara lika med en (då är antalet matchningar lika med partitionsfunktionen), såväl som grafens vikter , och icke-triviala vikter visas först efter att vertexborttagningen har tillämpats lemma. Men i grafen som erhålls efter alla möjliga raderingar av hörn , är alla vikter på kanterna lika med antingen , eller , och kanterna med vikt ingår nödvändigtvis i någon matchning. Dessutom, efter att ha kasserat kanterna, visar sig vikten vara lika med den aztekiska diamantgrafen i föregående ordning, endast med vikten av varje kant reducerad med hälften (och exakt dess kanter deltar i varje matchning). Detta tillåter oss att härleda den rekursiva formeln: [9] $G_{n}$ ${\displaystyle {\tilde {G_{n))))$ ${\tilde {G_{n}}}^{*}$ $ett$ ${\frac {1}{2))$ $ett$ ${\tilde {G_{n}}}^{*}$ $ett$ ${\displaystyle 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)

Bevis i form av Schroeder-nummer

Ett annat sätt att bevisa det är att tilldela varje partition av den aztekiska diamanten en uppsättning osammanhängande Schroeder-banor en-till-en . Då visar sig antalet möjliga partitioner vara lika med antalet sådana uppsättningar. $n$ $n$

För att göra detta räcker det med att markera mitten av de vertikala segmenten i den nedre vänstra delen av diamantgränsen och sedan rita linjer från dem, varje gång du ritar ett nytt segment symmetriskt i förhållande till mitten av dominon, där segment är placerat - horisontellt för horisontellt liggande plattor och i vinkel för vertikala plattor. Sedan, om vi fortsätter varje väg utanför diamanten med lutande linjer till samma nivå, får vi bara icke-korsande Schroeder-banor (varje väg längs diamanten kommer garanterat att sluta på samma horisontella linje där den började). $n$

Dessutom visar sig antalet sådana uppsättningar vara lika med determinanten för Hankel-matrisen som består av Schroeder-tal . Med tanke på små Schroeder-banor (det vill säga de där de horisontella segmenten inte ligger på nivå 0) och antalet av deras uppsättningar utan skärningspunkter (det kommer också att uttryckas av Hankel-matrisen, men för en annan sekvens), kan vi härleda relationer och , från vilka det är lätt att få ett rekursivt uttryck för [ 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)

Bevis genom att flytta en kedja av korsande dominobrickor

I detta bevis görs en aztekisk diamant först till en ny figur genom att skära ut fyra celler. Dessutom uppfyller de skurna cellerna följande villkor:

i schackfärgning är två av dem vita och två är svarta;
när man skär ut alla svarta och vita celler, bestäms plattsättningen av celler nära hälften av gränsen unikt, så att den återstående delen är en aztekisk diamant av ordning ; $n-1$
när man skär ut fyra celler bestäms orienteringen av alla dominobrickor som rör gränsen unikt, så att den återstående delen är en aztekisk diamant av ordning . $n-2$

Med tanke på ett godtyckligt par av partitioner av själva diamanten och en figur med fyra utskurna celler, kan man urskilja en kedja av korsande dominobrickor som går från en cell till en annan (dominoer från en och en annan partition växlar, två intilliggande dominobrickor skär varandra i en cell ). Sedan, genom att byta delar av denna kedja från en partition och från en annan, kan man få partitioner av två figurer, som var och en har endast två celler utskurna. Detta ger upprepningsrelationen [4]

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

Med samma metod kan du härleda en kort formel för ett särskilt fall av genereringsfunktionen (se nedan):

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

Genererar funktion för partitioner

Låt beteckna rangen för splittringen , och - halva antalet vertikala brickor i denna delning (antalet vertikala brickor är alltid jämnt, eftersom varje horisontell heltalslinje delar diamanten i två delar med ett jämnt antal celler i varje - vilket betyder att varje sådan horisontell linje korsas av ett jämnt antal vertikala brickor) . $r(T)$ $T$ $v(T)$

I Elkis , Kuperbergs, Larsens och Propps arbete övervägdes en genererande funktion , där summeringen utförs över alla möjliga partitioner av den aztekiska ordningens diamant . Det hittades i verket att . $AD(n;x,q)=\summa \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))$

I synnerhet följer den vanliga formeln för antalet partitioner från denna identitet: $AD(n;1,1)=\prod \limits _{k=0}^{n-1}2^{nk}=2^{\frac {n(n+1)}{2} }$

Slumpmässiga uppdelningar

Algoritm för att generera en slumpmässig partition

Det finns en välkänd algoritm för det lika sannolika valet av en slumpmässig uppdelning av en diamant av en given storlek från alla delningar av en sådan storlek. [6] [11]

För att generera en slumpmässig storleksdelning använder algoritmen en förgenererad slumpmässig aztekisk diamantdelning och transformerar den på ett speciellt sätt med ytterligare slumpmässighet. För att generera en slumpmässig storleksdelning måste du alltså konsekvent generera storleksdelningar . $n$ $n-1$ $n$ $1,2,\dots ,n-1,n$

Förvandlingen i övergången från storlek till omfattar tre steg: $n-1$ $n$

Förstörelse. Följande par av brickor (om några) tas bort från splittringen:
- plattan S, som är i kontakt med bottenytan av celltyp N;
- kakel E, som är i kontakt med höger sida av kakel typ W.
Flytta. Alla återstående brickor flyttas med en cell enligt deras typ i standardnotation - N upp, S ner, E höger, W vänster. Det föregående steget av förstörelse säkerställer att det inte blir någon överlappning av en bricka på en annan.
Generation. Det är bevisat att som ett resultat av de två föregående stegen kan alla tomma celler i området för den aztekiska diamantstorleken delas upp i 2x2 rutor. Vid genereringsstadiet fylls varje sådan ruta separat med antingen två vertikala eller två horisontella brickor med lika sannolikhet. $n$

Arctic Circle Theorem

Betrakta en cirkel inskriven i en kvadrat som avgränsar en aztekisk diamant. Hon skär av fyra hörn av torget. Det visar sig att för en slumpmässigt vald plattsättning, med mycket hög sannolikhet, kommer nästan alla dominobrickor som faller in i dessa hörn, dvs utanför denna cirkel, att "frysas": i de nedre och övre hörnen kommer de alla att vara horisontella, och i de vänstra och högra hörnen kommer de att vara vertikala. Tvärtom, beteendet hos plattsättningen inuti denna cirkel kan inte förutsägas - det är kaotiskt. Allt ovanstående utgör påståendet om polcirkelsatsen, bevisad 1995 av W. Jokush, J. Propp och P. Shor [12] [3] :

Låt vara sannolikheten att, med en slumpmässig färgning av en diamant av ordning , kommer alla brickor utanför cirkeln förstorade när de väl är inskrivna i denna diamant att placeras på ett deterministiskt sätt, det vill säga på den övre kanten kommer alla celler att vara från klass N, längst ner - från klass S, till höger - från klass W, till vänster - från klass E. ${\displaystyle p_{n,\varepsilon ))$ $n$ $1+\varepsilon$

Sedan för eventuella spärrar för . $\varepsilon >0$ $p_{n,\varepsilon }\to 1$ $n\till\infty$

Faktum är att satsen säger att i slumpmässiga partitioner av tillräckligt stora diamanter, kommer nästan hela regionen utanför den inskrivna cirkeln att fyllas exakt, som triviala partitioner.

Anteckningar

↑ Smirnov, 2015 , sid. 5.
↑ 1 2 3 Noam Elkies, Greg Kuperberg, Michael Larsen, James Propp. Alternerande teckenmatriser och dominobeläggningar // arXiv:math/9201305. — 1991-05-31. Arkiverad från originalet den 25 mars 2018.
↑ 1 2 William Jockusch, James Propp, Peter Shor. Random Domino Tilings and the Arctic Circle Theorem // arXiv:math/9801068. — 1998-01-13. Arkiverad från originalet den 25 september 2017.
↑ 1 2 Kokhas, 2008 .
↑ Smirnov, 2015 .
↑ 1 2 "", Eric Nordenstam, "", Vol. 15 (2010), papper nr. 3, sidor. Om blandningsalgoritmen för Domino Tilings // Electronic Journal of Probability. - 2010. - Vol. 15. - S. 75-95. Arkiverad från originalet den 25 mars 2018.
↑ För skolbarn. 013. Small ShAD - Asymptotiska problem med kombinatorik - Victor Kleptsyn . YouTube (22 april 2015). Hämtad: 24 mars 2018. (obestämd)
↑ Smirnov, 2015 , sid. 7-24.
↑ Smirnov, 2015 , sid. 25-32.
↑ Smirnov, 2015 , sid. 33-42.
↑ Eric Nordenstam. Om blandningsalgoritmen för Domino Tilings // arXiv:0802.2592 [math]. — 2008-02-19. Arkiverad från originalet den 25 mars 2018.
↑ Smirnov, 2015 , sid. 46.

Litteratur

Smirnov, E.Yu. Tre synpunkter på den aztekiska diamanten . — M .: MTsNMO , 2015. — 48 sid. - ISBN 978-5-4439-0279-1 .
K. Kokhas. Dela aztekiska diamanter och rutor i domino // Notes of Scientific Seminars POMI. - 2008. - T. 360 . - S. 180-230 .

Länkar

Burkard Polster. ARCTIC CIRCLE THEOREM eller varför spelar fysiker domino? . Matolog . YouTube-video (2020-12-24). Hämtad: 28 december 2020. (obestämd)