Pavare domino

model geometric

Î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ă.

Pavare domino a unui pătrat 8×8

Funcții de înălțime

modificare

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

modificare

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

modificare
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   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ă.

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.

  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)

Bibliografie

modificare
  • 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ă

modificare