Pavare domino
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Pavage_domino.svg/220px-Pavage_domino.svg.png)
În geometrie o pavare domino a unei regiuni din planul euclidian este o pavare a regiunii cu dominouri, forme formate prin unirea a două pătrate unitate care se întâlnesc latură la latură.
Funcții de înălțime
Pentru unele clase de piese aflate pe o grilă bidimensională regulată este posibil să se definească o funcție de înălțime care să asocieze un număr întreg la nodurile grilei. De exemplu, se desenează o tablă de șah, se alege un nod cu înălțimea 0. Atunci pentru orice nod există o cale de la la acesta. Pe această cale se definește înălțimea fiecărui nod (adică colțurile pătratelor) să fie înălțimea nodului anterior plus unu dacă pătratul din dreapta traseului de la la este negru, respectiv minus unu în caz contrar.[1]
Condiția Thurston pentru înălțime
Thurston descrie un test pentru a determina dacă o regiune din plan simplu conexă, formată din pătrate unitate alăturate, are o pavare domino. El formează un graf nedirecționat care are ca noduri punctele (x,y,z) din rețeaua tridimensională cu coordonate întregi, unde fiecare astfel de punct este conectat la patru vecini: dacă x + y este par, atunci (x,y,z) este conectat 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 este impar, atunci ( x,y,z) este conectat la (x + 1,y,z − 1), (x − 1, y,z − 1), (x,y + 1,z + 1) și (x,y − - 1,z + 1). Frontiera regiunii, văzută ca un șir de puncte întregi în planul (x,y), se ridică în mod unic (odată ce este aleasă o înălțime de pornire) la o cale în acest graf tridimensional. O condiție necesară pentru ca această regiune să fie pavabilă este ca această cale să se închidă pentru a forma o curbă simplă închisă tridimensională, însă această condiție nu este suficientă. Folosind o analiză mai atentă a traseului frontierei, Thurston a oferit un criteriu de pavabilitate a unei regiuni care a fost necesar și suficient.[2]
Numărul pavărilor regiunilor
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/Dominoes_tiling_8x8.svg/192px-Dominoes_tiling_8x8.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Pavare_domino.jpg/192px-Pavare_domino.jpg)
Drepta:Pavare domino cu model 4x4
Numărul de moduri de a acoperi un dreptunghi cu dominouri, calculat independent de Temperley și Fisher este:[3][4]
Când ambele m și n sunt impare, formula dă numărul corect de zero posibilități de pavaări domino.
Un caz particular apare la pavarea unui dreptunghi cu n piese de domino: soluția este șirul Fibonacci.[5]
Alt caz particular apare la pavarea pătratelor cu m = n = 0, 2, 4, 6, 8, 10, 12, ..., numerele soluțiilor fiind:[6]
- 1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ...
Aceste numere pot fi găsite scriind forma Pfaff a unei matrice antisimetrice(d) ale cărei valori proprii pot fi găsite în mod explicit. Această tehnică poate fi aplicată la multe subiecte legate de matematică.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a6/Diamant_azteque.svg/192px-Diamant_azteque.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/20/Diamant_azteque_plein.svg/192px-Diamant_azteque_plein.svg.png)
Numărul de pavări al unei regiuni depinde foarte mult de forma conturului și se poate schimba dramatic cu modificări aparent nesemnificative ale formei regiunii. Acest lucru este ilustrat de numărul de pavări ale unui diamant aztec(d) de ordinul n, unde numărul de pavări este 2(n + 1)n /2. Dacă acesta este înlocuit cu „diamantul aztec augmentat” de ordinul n cu 3 rânduri orizontale lungi în mijloc, în loc de 2, numărul de pavări scade la numărul mult mai mic D(n,n ), un număr Delannoy, care are doar creștere exponențială, nu una hiperexponențială în n. Pentru „diamantul aztec redus” de ordinul n cu un singur rând orizontal lung la mijloc, există o singură pavare.
Note
- ^ Kenyon, Okounkov, 2005
- ^ Thurston, 1990
- ^ Temperley, Fisher, 1961
- ^ Șirul A099390 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
- ^ Klarner, Pollack, 1980
- ^ Șirul A004003 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
Bibliografie
- en Barahona, Francisco (), „On the computational complexity of Ising spin glass models”, Journal of Physics A: Mathematical and General, 15 (10): 3241–3253, Bibcode:1982JPhA...15.3241B, doi:10.1088/0305-4470/15/10/028, MR 0684591
- en Erickson, Alejandro; Ruskey, Frank (), „Domino tatami covering is NP-complete”, În Lecroq, Thierry; Mouchard, Laurent, Combinatorial Algorithms: 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers, Lecture Notes in Computer Science, 8288, Heidelberg: Springer, pp. 140–149, arXiv:1305.6669
, doi:10.1007/978-3-642-45278-9_13, MR 3162068
- en Kasteleyn, P.W. (), „The statistics of dimers on a lattice, I: The number of dimer arrangements on a quadratic lattice”, Physica, 27 (12): 1209–1225, Bibcode:1961Phy....27.1209K, doi:10.1016/0031-8914(61)90063-5
- en Kenyon, Richard; Okounkov, Andrei (), „What is ... a dimer?” (PDF), Notices of the American Mathematical Society, 52 (3): 342–343
- en Klarner, David; Pollack, Jordan (), „Domino tilings of rectangles with fixed width”, Discrete Mathematics, 32 (1): 45–52, doi:10.1016/0012-365X(80)90098-9
, MR 0588907, Zbl 0444.05009
- en Thurston, W.P. (), „Conway's tiling groups”, American Mathematical Monthly, Mathematical Association of America, 97 (8): 757–773, doi:10.2307/2324578, JSTOR 2324578
- en Temperley, H. N.V.; Fisher, Michael E. (), „Dimer problem in statistical mechanics – an exact result”, Philosophical Magazine, 6 (68): 1061–1063, Bibcode:1961PMag....6.1061T, doi:10.1080/14786436108243366
Lectură suplimentară
- en Bodini, Olivier; Latapy, Matthieu (), „Generalized tilings with height functions” (PDF), Morfismos, 7 (1): 47–68, arXiv:2101.08347
, arhivat din original (PDF) la , accesat în
- en Faase, F. J. (), „On the number of specific spanning subgraphs of the graphs ”, Ars Combinatoria, 49: 129–154, MR 1633083
- en Hock, J. L.; McQuistan, R. B. (), „A note on the occupational degeneracy for dimers on a saturated two-dimenisonal lattice space”, Discrete Applied Mathematics, 8: 101–104, doi:10.1016/0166-218X(84)90083-0, MR 0739603
- en Kenyon, Richard (), „The planar dimer model with boundary: a survey”, În Baake, Michael; Moody, Robert V., Directions in mathematical quasicrystals, CRM Monograph Series, 13, American Mathematical Society, pp. 307–328, ISBN 0-8218-2629-8, MR 1798998
- en Propp, James (), „Lambda-determinants and domino-tilings”, Advances in Applied Mathematics, 34 (4): 871–879, arXiv:math.CO/0406301
, doi:10.1016/j.aam.2004.06.005
- en Sellers, James A. (), „Domino tilings and products of Fibonacci and Pell numbers”, Journal of Integer Sequences, 5 (Article 02.1.2): 12, Bibcode:2002JIntS...5...12S
- en Stanley, Richard P. (), „On dimer coverings of rectangles of fixed width”, Discrete Applied Mathematics, 12: 81–87, doi:10.1016/0166-218x(85)90042-3
, MR 0798013
- en Wells, David (), The Penguin Dictionary of Curious and Interesting Numbers (ed. revised), London: Penguin, p. 182, ISBN 0-14-026149-4
![]() | Portal Matematică |