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 |
Summary: | 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. |
---|---|
ISSN: | 1818-1015 2313-5417 |