Pavare domino

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

Format:Imagine multiplă Numărul de moduri de a acoperi un dreptunghi m×n cu mn2 dominouri, calculat independent de Temperley și Fisher este:[3][4]

∏j=1⌈m2⌉∏k=1⌈n2⌉(4cos2πjm+1+4cos2πkn+1).

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

Un caz particular apare la pavarea unui dreptunghi 2×n cu Format:Mvar piese de domino: soluția este șirul Fibonacci.[5]

Alt caz particular apare la pavarea pătratelor cu Format:Math, numerele soluțiilor fiind:[6]

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ...

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

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

Note

  1. ↑ Kenyon, Okounkov, 2005
  2. ↑ Thurston, 1990
  3. ↑ Temperley, Fisher, 1961
  4. ↑ Format:OEIS
  5. ↑ Klarner, Pollack, 1980
  6. ↑ Format:OEIS

Bibliografie

Lectură suplimentară

Format:Portal Format:Teselări

Adus de la „https://ro.wiki.beta.math.wmflabs.org/w/index.php?title=Pavare_domino&oldid=3316”