Mozaic domino

O placă de plăci de domino într-o regiune din planul euclidian  este un mozaic de plăci de domino , care sunt formate prin unirea a două pătrate unitare conectate de-a lungul unei margini. În mod echivalent, este o potrivire în graficul reticulat format prin plasarea unui vârf în centrul fiecărui pătrat al ariei și conectarea a două vârfuri dacă cele două pătrate corespunzătoare sunt adiacente.

Popularul canal matematic de YouTube Mathologer are un videoclip pe tema partițiilor de domino [1] .

Funcții de înălțime

Pentru unele clase de plăci pe o rețea obișnuită în spații bidimensionale, se poate defini o funcție de înălțime care atribuie un număr întreg fiecărui vârf al rețelei. De exemplu, să desenăm o tablă de șah, să fixăm un punct cu o înălțime de 0, apoi pentru orice vârf există o cale de la el. Pe această cale, definim înălțimea fiecărui vârf (adică vârfurile pătratelor) ca înălțimea vârfului anterior plus unu dacă pătratul este în dreapta de-a lungul căii de la negru și minus unul în caz contrar.

Informații mai detaliate pot fi găsite în lucrarea lui Kenion și Okunkov [2] .

Condiția de înălțime a lui Thurston

William Paul Thurston (1990) descrie un test pentru a determina dacă o regiune pur și simplu conectată formată prin unirea pătratelor unităților în plan are o teselație domino. Formează un grafic nedirecționat care are ca vârfuri puncte ( x , y , z ) într-o rețea de numere întregi tridimensionale și fiecare punct este legat de patru învecinate: dacă x  +  y este par, atunci ( x , y , z ) se conectează la ( x  + 1, y , z  + 1), ( x  − 1, y , z  + 1), ( x , y  + 1, z  − 1) și ( x , y  − 1, z  − 1 ), în timp ce dacă x  +  y ( x , y , z ) este impar, se conectează la ( x  + 1, y , z  − 1), ( x  − 1, y , z  − 1), ( x , y  + 1, z  + 1) și ( x , y  − 1, z  + 1). Limita unei regiuni, considerată ca o secvență de puncte întregi în plan ( x , y ), este ridicată în mod unic (dată fiind o înălțime inițială dată) la o cale în acest grafic 3D. O condiție necesară pentru existența unei plăci a zonei cu plăci de domino este închiderea căii (adică calea rezultată trebuie să formeze o curbă simplă închisă). Cu toate acestea, această condiție nu este suficientă. Folosind o analiză mai atentă a graniței, Thurston a dat un criteriu necesar și suficient pentru existența unei plăci a unui domeniu.

Numărarea plăcilor din zonă

Numărul de moduri de plasare a unui dreptunghi cu domino a fost calculat independent în 1961 de Temperley și Fisher [3] și Castellain [4] și acest număr este egal cu

Dacă m și n sunt ambele impare, formula oferă corect un număr zero de posibile plăci de domino.

Un caz special este teselarea unui dreptunghi cu n piese de domino, rezultând șirul Fibonacci (secvența A000045 în OEIS ) [5] .

Un alt caz special apare pentru pătratele cu m = n = 0, 2, 4, 6, 8, 10, 12, … - 1, 2, 36, 6728, 12988816 , 258584046368 , 5306047752196000040 , …

Aceste numere pot fi găsite prin scrierea lor ca Pfaffian al unei matrice oblice-simetrice , ale cărei valori proprii pot fi găsite în mod explicit. Această tehnică poate fi aplicată la multe obiecte matematice, cum ar fi calculul clasic bidimensional al funcției de corelație dimer-dimer în mecanica statistică .

Numărul de plăci ale unei regiuni este foarte sensibil la condițiile de limită și se poate schimba semnificativ cu modificări aparent nesemnificative ale formei regiunii. Acest lucru poate fi ilustrat prin numărul de plăci diamantate aztece de ordinul n , unde numărul de plăci este 2 ( n  + 1) n /2 . Dacă este înlocuit cu un „diamant aztec extins” de ordinul n cu trei rânduri lungi în mijloc în loc de două, numărul de plăci scade la un număr mult mai mic D( n , n ), numărul Delannoy , care are doar exponențial. , nu creștere super-exponențială cu n . Pentru un „diamant aztec redus” de ordinul n cu un singur rând lung din mijloc, există o singură terasare.

• Ordinul 4 diamant aztec, cu 1024 plăci

• Una dintre posibilele plăci

Vezi și

• Mecanica statistica
• Câmp liber gaussian
• Dominouri (poliominouri) , problema tablei de șah „Mutilate”.

Note

1. ↑ Video pe canalul YouTube Mathologer
2. ↑ Kenyon, Okounkov, 2005 , p. 342–343.
3. ↑ Temperley, Fisher, 1961 .
4. ↑ Kasteleyn, 1961 .
5. ↑ Klarner și Pollack 1980 , p. 45–52.

Link -uri

• Videoclip popular pe canalul YouTube Mathologer

Literatură

• Olivier Bodini, Matthieu Latapy. Placuri generalizate cu funcții de înălțime  // Morfismos. - 2003. - T. 7 , nr. 1 . — p. 47–68 . — ISSN 1870-6525 . Arhivat din original pe 10 februarie 2012. .
• F. Faase. Despre numărul de subgrafe specifice de întindere ale graficelor GX P_n // Ars Combin .. - 1998. - T. 49 . — S. 129–154 .
• JL Hock, R.B. McQuistan. O notă despre degenerarea ocupațională pentru dimeri pe un spațiu de rețea bidimensional saturat // Aplicație discretă. Matematică.. - 1984. - V. 8 . — S. 101–104 . - doi : 10.1016/0166-218X(84)90083-0 .
• PW Kasteleyn. Statistica dimerilor pe o rețea. I. Numărul de aranjamente de dimeri pe o rețea pătratică // Physica . - 1961. - T. 27 , nr. 12 . — S. 1209–1225 . - doi : 10.1016/0031-8914(61)90063-5 . - Cod biblic . .
• Richard Kenyon. Direcții în cvasicristale matematice / Michael Baake, Robert V. Moody. - Providence, RI: Societatea Americană de Matematică , 2000. - Vol. 13 . — S. 307–328 . — ISBN 0-8218-2629-8 .
• Richard Kenyon, Andrei Okounkov. Ce este... un dimer?  // Anunțuri ale Societății Americane de Matematică . - 2005. - T. 52 , nr. 3 . - P. 342-343. — ISSN 0002-9920 . .
• David Klarner, Jordan Pollack. Piese de domino de dreptunghiuri cu lățime fixă ​​// Matematică discretă . - 1980. - T. 32 , nr. 1 . - doi : 10.1016/0012-365X(80)90098-9 . .
• Richard J. Pavajul regiunilor dreptunghiulare cu plăci dreptunghiulare: plăci de tatami și non-tatami. — 2013.
• Lambda-determinanți și domino-tilings // Progrese în matematică aplicată . - 2005. - T. 34 , nr. 4 . — S. 871–879 . - doi : 10.1016/j.aam.2004.06.005 . - arXiv : math.CO/0406301 . .
• Frank Ruskey, Jennifer Woodcock. Numărarea plăcilor Tatami cu înălțime fixă. - 2009. - T. 16 , nr. 1 . - S. R126 .
• James A. Sellers. Piese de domino și produse ale numerelor Fibonacci și Pell  // Journal of Integer Sequences. - 2002. - V. 5 , nr. Articolul 02.1.2 . .
• Richard P Stanley. Pe acoperiri dimer ale dreptunghiurilor de lățime fixă ​​// Aplicație discretă. Matematică. - 1985. - T. 12 . — S. 81–87 . - doi : 10.1016/0166-218x(85)90042-3 .
• W. P. Thurston. Grupurile de gresie ale lui Conway. — American Mathematical Monthly . - Mathematical Association of America, 1990. - T. 97. - S. 757-773. - doi : 10.2307/2324578 . .
• David Wells. Dicționarul Pinguin al numerelor curioase și interesante . - Londra: Penguin, 1997. - P.  182 . — ISBN 0-14-026149-4 . .
• HNV Temperley, Michael E. Fisher. Problemă dimer în mecanica statistică-un rezultat exact // Philosophical Magazine. - 1961. - T. 6 , nr. 68 . — S. 1061–1063 . - doi : 10.1080/14786436108243366 .