Domino mosaik

En flisebelægning af domino - fliser i en region i det euklidiske plan  er en mosaik af domino - fliser , som er dannet af foreningen af ​​to enhedsfirkanter forbundet langs en kant. Tilsvarende er det en matchning i gittergrafen dannet ved at placere et toppunkt i midten af ​​hvert kvadrat i området og forbinde to toppunkter, hvis de to tilsvarende kvadrater er tilstødende .

Den populære matematiske YouTube -kanal Mathologer har en video om emnet domino-partitioner [1] .

Højdefunktioner

For nogle klasser af flisebelægninger på et regulært gitter i todimensionale rum kan man definere en højdefunktion, der tildeler et heltal til hvert hjørne af gitteret. Lad os for eksempel tegne et skakbræt, fikse et punkt med en højde på 0, så er der for ethvert vertex en sti fra til det. På denne sti definerer vi højden af ​​hvert toppunkt (det vil sige kvadraternes toppunkter) som højden af ​​det forrige toppunkt plus én, hvis kvadratet er til højre langs stien fra til sort, og minus én ellers.

Mere detaljerede oplysninger kan findes i papiret af Kenion og Okunkov [2] .

Thurstons højdetilstand

William Paul Thurston (1990) beskriver en test til at bestemme, om et simpelt forbundet område dannet af foreningen af ​​enhedskvadrater i planet har en domino-tesselation. Den danner en urettet graf , der har som toppunkter ( x , y , z ) i et tredimensionelt heltalsgitter , og hvor hvert punkt er forbundet med fire tilstødende: hvis x  +  y er lige, så ( x , y , z ) forbinder til ( x  + 1, y , z  + 1), ( x  − 1, y , z  + 1), ( x , y  + 1, z  − 1) og ( x , y  − 1, z  − 1 ), mens hvis x  +  y ( x , y , z ) er ulige, forbindes til ( x  + 1, y , z  − 1), ( x  − 1, y , z  − 1), ( x , y  + 1, z  + 1) og ( x , y  - 1, z  + 1). Grænsen for et område, betragtet som en sekvens af heltalpunkter i planet ( x , y ), løftes unikt (givet en given starthøjde) til en sti i dette 3D-plot. En nødvendig betingelse for eksistensen af ​​en flisebelægning af området med dominofliser er stiens lukkethed (det vil sige, at den resulterende sti skal danne en simpel lukket kurve). Denne betingelse er dog ikke tilstrækkelig. Ved at bruge en mere omhyggelig analyse af grænsen gav Thurston et nødvendigt og tilstrækkeligt kriterium for eksistensen af ​​en flisedeling af et domæne.

Tælle areal flisebelægninger

Antallet af måder at flisebelægge et rektangel med dominobrikker blev beregnet uafhængigt i 1961 af Temperley og Fisher [3] og Castellain [4] og dette tal er lig med

Hvis m og n begge er ulige, giver formlen korrekt nul antal mulige domino-fliser.

Et særligt tilfælde er tesselleringen af ​​et rektangel med n dominobrikker, hvilket resulterer i Fibonacci-sekvensen (sekvens A000045 i OEIS ) [5] .

Et andet specialtilfælde opstår for kvadrater med m = n = 0, 2, 4, 6, 8, 10, 12, … - 1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, … ( OE3 sekvens , … ( 03 sekvens, A3 ).

Disse tal kan findes ved at skrive dem som Pfaffian af en skæv-symmetrisk matrix , hvis egenværdier kan findes eksplicit. Denne teknik kan anvendes på mange matematiske objekter, såsom den klassiske 2-dimensionelle beregning af dimer-dimer-korrelationsfunktionen i statistisk mekanik .

Antallet af flisebelægninger i et område er meget følsomt over for randbetingelserne og kan ændre sig væsentligt med tilsyneladende ubetydelige ændringer i regionens form. Dette kan illustreres ved antallet af aztekiske diamantfliser af orden n , hvor antallet af flisebelægninger er 2 ( n  + 1) n /2 . Hvis den erstattes af en "udvidet aztekisk diamant" af orden n med tre lange rækker i midten i stedet for to, falder antallet af flisebelægninger til et meget mindre tal D( n , n ), Delannoy-tallet , som kun har eksponentiel , ikke supereksponentiel vækst med n . For en "reduceret Aztec-diamant" af orden n med kun én lang midterste række, er der kun én flisebelægning.

• Aztec diamant orden 4, med 1024 fliser

• En af de mulige flisebelægninger

Se også

• Statistisk mekanik
• Gaussisk frifelt
• Dominoer (polyominoer) , problemet med "Mutilated" skakbræt

Noter

1. ↑ Video på YouTube-kanalen Mathologer
2. ↑ Kenyon, Okounkov, 2005 , s. 342-343.
3. ↑ Temperley, Fisher, 1961 .
4. ↑ Kasteleyn, 1961 .
5. ↑ Klarner og Pollack 1980 , s. 45-52.

Links

• Populær video på YouTube-kanalen Mathologer

Litteratur

• Olivier Bodini, Matthieu Latapy. Generaliserede flisebelægninger med  højdefunktioner // Morfismos. - 2003. - T. 7 , no. 1 . — s. 47–68 . — ISSN 1870-6525 . Arkiveret fra originalen den 10. februar 2012. .
• F. Faase. Om antallet af specifikke spændende undergrafer af graferne GX P_n // Ars Combin .. - 1998. - T. 49 . — S. 129–154 .
• JL Hock, R.B. McQuistan. En note om den erhvervsmæssige degeneration for dimerer på et mættet to-dimensionelt gitterrum // Discrete Appl. Math.. - 1984. - V. 8 . — S. 101–104 . - doi : 10.1016/0166-218X(84)90083-0 .
• PW Kasteleyn. Statistikken over dimerer på et gitter. I. Antallet af dimerarrangementer på et kvadratisk gitter // Physica . - 1961. - T. 27 , no. 12 . — S. 1209–1225 . - doi : 10.1016/0031-8914(61)90063-5 . - . .
• Richard Kenyon. Instruktioner i matematiske kvasikrystaller / Michael Baake, Robert V. Moody. - Providence, RI: American Mathematical Society , 2000. - Vol. 13 . — S. 307–328 . — ISBN 0-8218-2629-8 .
• Richard Kenyon, Andrei Okounkov. Hvad er ... en dimer?  // Meddelelser fra American Mathematical Society . - 2005. - T. 52 , no. 3 . - S. 342-343. — ISSN 0002-9920 . .
• David Klarner, Jordan Pollack. Domino flisebelægninger af rektangler med fast bredde // Diskret matematik . - 1980. - T. 32 , no. 1 . - doi : 10.1016/0012-365X(80)90098-9 . .
• Richard J. Brolægning af rektangulære områder med rektangulære fliser: tatami- og ikke-tatami-fliser. - 2013.
• Lambda-determinanter og domino-fliser // Fremskridt i anvendt matematik . - 2005. - T. 34 , no. 4 . — S. 871–879 . - doi : 10.1016/j.aam.2004.06.005 . - arXiv : math.CO/0406301 . .
• Frank Ruskey, Jennifer Woodcock. Tæller fasthøjde Tatami fliser. - 2009. - T. 16 , no. 1 . - S. R126 .
• James A. Sellers. Domino-fliser og produkter af Fibonacci- og Pell-numre  // Journal of Integer Sequences. - 2002. - V. 5 , no. Artikel 02.1.2 . .
• Richard P Stanley. På dimerbelægninger af rektangler med fast bredde // Diskret Appl. Matematik. - 1985. - T. 12 . — S. 81–87 . - doi : 10.1016/0166-218x(85)90042-3 .
• W.P. Thurston. Conways flisegrupper. — American Mathematical Monthly . - Mathematical Association of America, 1990. - T. 97. - S. 757-773. - doi : 10.2307/2324578 . .
• David Wells. Penguin Dictionary of Curious and Interesting Numbers . - London: Penguin, 1997. - S.  182 . — ISBN 0-14-026149-4 . .
• HNV Temperley, Michael E. Fisher. Dimer problem i statistisk mekanik - et nøjagtigt resultat // Philosophical Magazine. - 1961. - T. 6 , no. 68 . — S. 1061–1063 . - doi : 10.1080/14786436108243366 .