The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino

A. V. Shutov ; E. V. Kolomeykina

Modelirovanie i analiz informacionnyh sistem, Tome 20 (2013) no. 5, pp. 148-157

Résumé

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 $\mathbb{Z}^2$. It is proved that $2^{n-3}+2^{[\frac{n-3}{2}]}\leq T(n)\leq 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.

Détail

Keywords: tilings, polyomino.