The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino
We study a problem of a number of lattice plane tilings by given area polyominoes. A polyomino is a connected plane geometric figure formed by joining edge to edge a finite number of unit squares. A tiling is a lattice tiling if each tile can be mapped to any other tile by translation which maps the...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2013-10-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/179 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849240786854477824 |
|---|---|
| author | A. V. Shutov E. V. Kolomeykina |
| author_facet | A. V. Shutov E. V. Kolomeykina |
| author_sort | A. V. Shutov |
| collection | DOAJ |
| description | We study a problem of a number of lattice plane tilings by given area polyominoes. A polyomino is a connected plane geometric figure formed by joining edge to edge a finite number of unit squares. A tiling is a lattice tiling if each tile can be mapped to any other tile by translation which maps the whole tiling to itself. Let T(n) be a number of lattice plane tilings by given area polyominoes such that its translation lattice is a sublattice of Z². It is proved that 2n−3 + 2[ n−3 2 ] ≤ T(n) ≤ C(n + 1)3 (2.7)n+1. In the proof of a lower bound we give an explicit construction of required lattice plane tilings. The proof of an upper bound is based on a criterion of the existence of lattice plane tiling by polyomino and on the theory of self-avoiding walk. Also, it is proved that almost all polyominoes that give lattice plane tilings have sufficiently large perimeters. |
| format | Article |
| id | doaj-art-2c9a4e019c5e49a0bd497c8154390f25 |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2013-10-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-2c9a4e019c5e49a0bd497c8154390f252025-08-20T04:00:26ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172013-10-0120514815710.18255/1818-1015-2013-5-148-157173The Estimation of the Number of Lattice Tilings of a Plane by a Given Area PolyominoA. V. Shutov0E. V. Kolomeykina1Vladimir State UniversityMoscow State Technical UniversityWe study a problem of a number of lattice plane tilings by given area polyominoes. A polyomino is a connected plane geometric figure formed by joining edge to edge a finite number of unit squares. A tiling is a lattice tiling if each tile can be mapped to any other tile by translation which maps the whole tiling to itself. Let T(n) be a number of lattice plane tilings by given area polyominoes such that its translation lattice is a sublattice of Z². It is proved that 2n−3 + 2[ n−3 2 ] ≤ T(n) ≤ C(n + 1)3 (2.7)n+1. In the proof of a lower bound we give an explicit construction of required lattice plane tilings. The proof of an upper bound is based on a criterion of the existence of lattice plane tiling by polyomino and on the theory of self-avoiding walk. Also, it is proved that almost all polyominoes that give lattice plane tilings have sufficiently large perimeters.https://www.mais-journal.ru/jour/article/view/179tilingspolyomino |
| spellingShingle | A. V. Shutov E. V. Kolomeykina The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino Моделирование и анализ информационных систем tilings polyomino |
| title | The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino |
| title_full | The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino |
| title_fullStr | The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino |
| title_full_unstemmed | The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino |
| title_short | The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino |
| title_sort | estimation of the number of lattice tilings of a plane by a given area polyomino |
| topic | tilings polyomino |
| url | https://www.mais-journal.ru/jour/article/view/179 |
| work_keys_str_mv | AT avshutov theestimationofthenumberoflatticetilingsofaplanebyagivenareapolyomino AT evkolomeykina theestimationofthenumberoflatticetilingsofaplanebyagivenareapolyomino AT avshutov estimationofthenumberoflatticetilingsofaplanebyagivenareapolyomino AT evkolomeykina estimationofthenumberoflatticetilingsofaplanebyagivenareapolyomino |