thumb|Pavare domino a unui pătrat 8×8 Î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.Kenyon, Okounkov, 2005

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.Thurston, 1990

Numărul pavărilor regiunilor

Numărul de moduri de a acoperi un dreptunghi cu dominouri, calculat independent de Temperley și Fisher este:Temperley, Fisher, 1961

Când ambele și sunt impare, formula dă numărul corect de zero posibilități de pavaări domino.

Un caz particular apare la pavarea unui dreptunghi cu piese de domino: soluția este șirul Fibonacci.Klarner, Pollack, 1980

Alt caz particular apare la pavarea pătratelor cu , numerele soluțiilor fiind: 1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ...

Aceste numere pot fi găsite scriind forma Pfaff a unei ale cărei valori proprii pot fi găsite în mod explicit. Această tehnică poate fi aplicată la multe subiecte legate de matematică.

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 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 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 . Pentru „diamantul aztec redus” de ordinul cu un singur rând orizontal lung la mijloc, există o singură pavare.

Note

Bibliografie

Lectură suplimentară

Categorie:Pavări Categorie:Combinatorică