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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2013-01-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | http://mais-journal.ru/jour/article/view/179 |
| _version_ | 1797969671245266944 |
|---|---|
| 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. |
| first_indexed | 2024-04-11T03:05:52Z |
| format | Article |
| id | doaj.art-2ae9e14f14bb40689a091624b5fbfbbb |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-11T03:05:52Z |
| publishDate | 2013-01-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-2ae9e14f14bb40689a091624b5fbfbbb2023-01-02T13:06:28ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172013-01-01205148157173The Estimation of the Number of Lattice Tilings of a Plane by a Given Area PolyominoA. V. Shutov0E. V. Kolomeykina1Владимирский государственный университетМосковский государственный технический университет им. Н.Э.Баумана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.http://mais-journal.ru/jour/article/view/179разбиенияполимино |
| spellingShingle | A. V. Shutov E. V. Kolomeykina The Estimation of the Number of Lattice Tilings of a Plane by a Given Area 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 | разбиения полимино |
| url | http://mais-journal.ru/jour/article/view/179 |
| work_keys_str_mv | AT avshutov theestimationofthenumberoflatticetilingsofaplanebyagivenareapolyomino AT evkolomeykina theestimationofthenumberoflatticetilingsofaplanebyagivenareapolyomino AT avshutov estimationofthenumberoflatticetilingsofaplanebyagivenareapolyomino AT evkolomeykina estimationofthenumberoflatticetilingsofaplanebyagivenareapolyomino |