Dominó mozaik

Az euklideszi síkban  lévő régióban lévő dominólapok mozaikja dominólapkák mozaikja , amelyek két , egy él mentén összekapcsolt egységnégyzet egyesülésével jönnek létre . Ezzel egyenértékűen egy illesztés a rácsgráfban , amelyet úgy alakítunk ki, hogy a terület minden négyzetének közepébe egy csúcsot helyezünk, és két csúcsot összekapcsolunk, ha a két megfelelő négyzet szomszédos.

A népszerű matematikai YouTube -csatornán, a Mathologeren van egy videó a dominópartíciók témájában [1] .

Magasságfüggvények

A kétdimenziós terek szabályos rácsán lévő burkolólapok bizonyos osztályaihoz definiálhatunk egy magasságfüggvényt, amely a rács minden csúcsához egy egész számot rendel. Például rajzoljunk egy sakktáblát, rögzítsünk egy 0 magasságú pontot, majd bármelyik csúcshoz van egy út ahonnan oda vezet. Ezen az útvonalon az egyes csúcsok (vagyis a négyzetek csúcsai) magasságát úgy határozzuk meg, mint az előző csúcs magasságát plusz egy, ha a négyzet a feketébe vezető út jobb oldalán van , egyébként pedig mínusz egy.

Részletesebb információk Kenion és Okunkov [2] cikkében találhatók .

Thurston magassági állapota

William Paul Thurston (1990) egy tesztet ír le annak meghatározására, hogy a síkban lévő egységnégyzetek egyesítése által alkotott egyszerűen összefüggő régiónak van-e dominó tesszellációja. Irányítatlan gráfot alkot , amelynek csúcsai ( x , y , z ) egy háromdimenziós egészrácsban , és minden pontja négy szomszédos rácshoz kapcsolódik: ha x  +  y páros, akkor ( x , y , z ) az ( x  + 1, y , z  + 1), ( x  - 1, y , z  + 1), ( x , y  + 1, z  - 1) és ( x , y  - 1, z  - 1 ) -hoz kapcsolódik ), míg ha x  +  y ( x , y , z ) páratlan, akkor az ( x  + 1 , y , z  - 1 ), ( x  - 1 , y , z  - 1 ), ( x , y  + 1 , z  + 1) és ( x , y  − 1, z  + 1). Egy régió határa, amelyet a síkban ( x , y ) lévő egész pontok sorozatának tekintünk, ebben a 3D-s diagramban egyedileg emelkedik (adott kezdeti magassággal) egy útvonalra. A dominólapokkal ellátott terület burkolásának szükséges feltétele az út zártsága (azaz az így létrejövő útnak egyszerű zárt ívet kell alkotnia). Ez a feltétel azonban nem elegendő. Thurston a határ alaposabb elemzésével szükséges és elégséges kritériumot adott egy tartomány csempézettségének létezésére.

Területburkolások számlálása

Temperley és Fisher [3] , valamint Castellain [4] 1961-ben egymástól függetlenül számították ki, hogy egy téglalapot dominókkal lehet burkolni, és ez a szám egyenlő

Ha m és n is páratlan, a képlet helyesen ad nulla számú lehetséges dominócsempét.

Speciális eset egy téglalap tesszellációja n dominóval , ami a Fibonacci sorozatot eredményezi ( A000045 szekvencia az OEIS -ben ) [5] .

Egy másik speciális eset fordul elő azoknál a négyzeteknél, amelyeknél m = n = 0, 2, 4, 6, 8, 10, 12, … - 1, 2, 36, 6728, 12988816, 258584046368, 53060477521960003 (OEIS03, … A szekvencia ) .

Ezeket a számokat úgy találhatjuk meg, hogy egy ferde-szimmetrikus mátrix Pfaffiánjaként írjuk fel őket , amelynek sajátértékei kifejezetten megtalálhatók. Ez a technika számos matematikai objektumra alkalmazható, például a dimer-dimer korrelációs függvény klasszikus 2-dimenziós számításánál a statisztikai mechanikában .

Egy régió csempézéseinek száma nagyon érzékeny a peremfeltételekre, és a régió alakjának látszólag jelentéktelen változásaival jelentősen változhat. Ez szemléltethető az n rendű azték gyémánt burkolólapok számával, ahol a burkolólapok száma 2 ( n  + 1) n /2 . Ha egy n -es rendű "kiterjesztett azték gyémánttal" helyettesítjük, középen három hosszú sorral kettő helyett, a burkolólapok száma egy sokkal kisebb D( n , n ) számra csökken, a Delannoy-számra , amely csak exponenciális. , nem szuperexponenciális növekedés n -el . Egy n . rendű „csökkentett azték gyémánthoz”, amelyiknek csak egy hosszú középső sora van, csak egy burkolólap van.

• Azték gyémánt rendelés 4, 1024 csempével

• Az egyik lehetséges burkolat

Lásd még

• Statisztikai mechanika
• Gauss szabad mező
• Dominó (poliominó) , a "Megcsonkított" sakktábla probléma

Jegyzetek

1. ↑ Videó a YouTube Mathologer csatornán
2. ↑ Kenyon, Okounkov, 2005 , p. 342–343.
3. ↑ Temperley, Fisher, 1961 .
4. ↑ Kasteleyn, 1961 .
5. ↑ Klarner és Pollack 1980 , p. 45–52.

Linkek

• Népszerű videó a YouTube Mathologer csatornán

Irodalom

• Olivier Bodini, Matthieu Latapy. Általánosított burkolólapok magasságfüggvényekkel  // Morfismos. - 2003. - T. 7 , sz. 1 . – 47–68 . — ISSN 1870-6525 . Az eredetiből archiválva: 2012. február 10. .
• F. Faase. A GX P_n gráfok konkrét feszítő részgráfjainak számáról // Ars Combin .. - 1998. - T. 49 . – S. 129–154 .
• JL Hock, R.B. McQuistan. Megjegyzés a telített, kétdimenziós rácstérben lévő dimerek foglalkozási degenerációjához // Discrete Appl. Matek.. - 1984. - V. 8 . – S. 101–104 . - doi : 10.1016/0166-218X(84)90083-0 .
• PW Kasteleyn. Dimerek statisztikája rácson. I. A dimer elrendezések száma másodfokú rácson // Physica . - 1961. - T. 27 , sz. 12 . – S. 1209–1225 . - doi : 10.1016/0031-8914(61)90063-5 . - . .
• Richard Kenyon. Irányok a matematikai kvázikristályokban / Michael Baake, Robert V. Moody. - Providence, RI: American Mathematical Society , 2000. - 13. kötet . – S. 307–328 . — ISBN 0-8218-2629-8 .
• Richard Kenyon, Andrej Okounkov. Mi az… dimer?  // Az Amerikai Matematikai Társaság közleményei . - 2005. - T. 52 , sz. 3 . - P. 342-343. — ISSN 0002-9920 . .
• David Klarner, Jordan Pollack. Rögzített szélességű téglalapok dominócsempéi // Diszkrét matematika . - 1980. - T. 32 , sz. 1 . - doi : 10.1016/0012-365X(80)90098-9 . .
• Richard J. Téglalap alakú területek burkolása téglalap alakú csempével: tatami és nem tatami burkolólapok. — 2013.
• Lambda-determinánsok és dominócsempék // Advances in Applied Mathematics . - 2005. - T. 34 , sz. 4 . – S. 871–879 . - doi : 10.1016/j.aam.2004.06.005 . - arXiv : math.CO/0406301 . .
• Frank Ruskey, Jennifer Woodcock. Fix magasságú tatami burkolólapok számolása. - 2009. - T. 16 , sz. 1 . - S. R126 .
• James A. Sellers. Domino csempék és Fibonacci- és Pell-számok termékei  // Journal of Integer Sequences. - 2002. - V. 5 , sz. cikk 02.1.2 . .
• Richard P Stanley. Rögzített szélességű téglalapok dimer burkolatain // Discrete Appl. Math. - 1985. - T. 12 . – S. 81–87 . - doi : 10.1016/0166-218x(85)90042-3 .
• W. P. Thurston. Conway csempéző csoportjai. — American Mathematical Monthly . - Mathematical Association of America, 1990. - T. 97. - S. 757-773. - doi : 10.2307/2324578 . .
• David Wells. Érdekes és érdekes számok pingvin szótára . - London: Pingvin, 1997. -  182. o . — ISBN 0-14-026149-4 . .
• HNV Temperley, Michael E. Fisher. Dimer probléma a statisztikai mechanikában – pontos eredmény // Filozófiai Magazin. - 1961. - T. 6 , sz. 68 . – S. 1061–1063 . - doi : 10.1080/14786436108243366 .