Pavare domino

Î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 $A_{0}$ cu înălțimea 0. Atunci pentru orice nod există o cale de la $A_{0}$ la acesta. Pe această cale se definește înălțimea fiecărui nod $A_{n+1}$ (adică colțurile pătratelor) să fie înălțimea nodului anterior $A_{n}$ plus unu dacă pătratul din dreapta traseului de la $A_{n}$ la $A_{n+1}$ 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

Stânga: O pavare domino a unui pătrat de 8×8 cu numărul minim de perechi cu latura lungă la latura lungă (o singură pereche, în centru)
Drepta:Pavare domino cu model 4x4

Numărul de moduri de a acoperi un dreptunghi $m\times n$ cu ${\frac {mn}{2}}$ dominouri, calculat independent de Temperley și Fisher este:^[3]^[4]

\prod _{j=1}^{\lceil {\frac {m}{2}}\rceil }\prod _{k=1}^{\lceil {\frac {n}{2}}\rceil }\left(4\cos ^{2}{\frac {\pi j}{m+1}}+4\cos ^{2}{\frac {\pi k}{n+1}}\right).

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 $2\times n$ 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) $mn\times mn$ ale cărei valori proprii pot fi găsite în mod explicit. Această tehnică poate fi aplicată la multe subiecte legate de matematică.

Un diamant aztec de ordinul 4, care are 1024 de pavări domino

Una dintre pavările domino posibile

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 (1982), „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 (2013), „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. (1961), „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 (2005), „What is ... a dimer?” (PDF), Notices of the American Mathematical Society, 52 (3): 342–343
en Klarner, David; Pollack, Jordan (1980), „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. (1990), „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. (1961), „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 (2003), „Generalized tilings with height functions” (PDF), Morfismos, 7 (1): 47–68, arXiv:2101.08347  , arhivat din original (PDF) la 25 noiembrie 2021, accesat în 19 septembrie 2021
en Faase, F. J. (1998), „On the number of specific spanning subgraphs of the graphs $G\times P_{n}$ ”, Ars Combinatoria, 49: 129–154, MR 1633083
en Hock, J. L.; McQuistan, R. B. (1984), „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 (2000), „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 (2005), „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. (2002), „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. (1985), „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 (1997), The Penguin Dictionary of Curious and Interesting Numbers (ed. revised), London: Penguin, p. 182, ISBN 0-14-026149-4

Portal Matematică

[1] Kenyon, Okounkov, 2005

[2] Thurston, 1990

[3] Temperley, Fisher, 1961

[4] Șirul A099390 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

[5] Klarner, Pollack, 1980

[6] Șirul A004003 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

[1]

[2]

[3]

[4]

[5]

[6]