Geodesic
The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino
Modelirovanie i analiz informacionnyh sistem, Tome 20 (2013) no. 5, pp. 148-157.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: tilings, polyomino. 
@article{MAIS_2013_20_5_a8,
     author = {A. V. Shutov and E. V. Kolomeykina},
     title = {The {Estimation} of the {Number} of {Lattice} {Tilings} of a {Plane} by a {Given} {Area} {Polyomino}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {148--157},
     publisher = {mathdoc},
     volume = {20},
     number = {5},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2013_20_5_a8/}
}
TY  - JOUR
AU  - A. V. Shutov
AU  - E. V. Kolomeykina
TI  - The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2013
SP  - 148
EP  - 157
VL  - 20
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2013_20_5_a8/
LA  - ru
ID  - MAIS_2013_20_5_a8
ER  - 
%0 Journal Article
%A A. V. Shutov
%A E. V. Kolomeykina
%T The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino
%J Modelirovanie i analiz informacionnyh sistem
%D 2013
%P 148-157
%V 20
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2013_20_5_a8/
%G ru
%F MAIS_2013_20_5_a8
A. V. Shutov; E. V. Kolomeykina. The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino. Modelirovanie i analiz informacionnyh sistem, Tome 20 (2013) no. 5, pp. 148-157. http://geodesic.mathdoc.fr/item/MAIS_2013_20_5_a8/

[1] S. W. Golomb, Polyominoes, 1996, 198 pp. | Zbl

[2] S. W. Golomb, “Checkerboards and polyominoes”, Amer. Math. Monthly, 61 (1954), 672–682 | MR

[3] M. Gardner, Mathematical puzzles and diversions, The University of Chicago press, 1987

[4] M. Gardner, Mathematical Recreations: A Collection in Honor of Martin Gardner, Dover, 1998 | MR

[5] M. Gardner, Mathematical Carnival: A New Round-up of Tantalizers and Puzzles from «Scientific American», Knopf Publishing Group, 1975 | Zbl

[6] M. Gardner, Time Travel and Other Mathematical Bewilderments, W. H. Freeman and Company, 1987 | MR | MR

[7] D. Klarner, “A Cell growth problems”, Cand. J. Math., 19 (1967), 851–863 | DOI | MR | Zbl

[8] G. Barequet, M. Moffie, A. Rib, G. Rote, “Counting polyominoes on twisted cylinders”, Integers, 6 (2006), A22 | MR | Zbl

[9] D. A. Klarner, R. L. Rivest, “A procedure for improving the upper bound for the number of n-ominoes”, Canad. J. Math., 25 (1973), 585–602 | DOI | MR | Zbl

[10] I. Jensen, “Counting polyominoes: A parallel implementation for cluster computing”, Lecture Notes in Computer Science, 2659, 2003, 203–212 | DOI

[11] M. Bousquet-Melou, R. Brak, “Exactly Solved Models”, In Polygons, Polyominoes and Polycubes, Lecture Notes in Physics, ed. A. J. Guttman, Springer, 2009, 43–78 | DOI | MR | Zbl

[12] C. Rhoads Glenn, “Planar tilings by polyominoes, polyhexes, and polyiamonds”, Journal of Computational and Applied Mathematics, 2005, 329–353 | DOI | MR | Zbl

[13] G. C. Rhoads, Planar Tilings and the Search for an Aperiodic, Prototile: PhD dissertation, Rutgers University, 2003

[14] J. Myers http://www.srcf.ucam.org/ ̃ jsm28/tiling/

[15] R. Ammann, B. Grunbaum, G. Shephard, “Aperiodic tiles”, Discrete and Computational Geometry, 6 (1991), 1–25 | DOI | MR

[16] Maleev A. V., “Algorithm and Computer-Program Search for Variants of Polyomino Packings in Plane”, Crystallography, 58:5 (2013), 749–756 (in Russian) | DOI

[17] Srecko Brlek, Andrea Frosini, Simone Rinaldi, Laurent Vuillon, “Tilings by translation: enumeration by a rational language approach”, The electronic journal of combinatorics, 13 (2006), R15 | MR | Zbl

[18] Ian Gambini, Laurent Vuillon, “An algorothm for deciding if a polyomino tiles the plane by translations”, RAIRO — Theoretical Informatics and Applications, 41:2 (2007), 147–155 | DOI | MR | Zbl

[19] S. Brlek, X. Provencal, J.-M. Fedou, “On the tiling by translation problem”, Discrete Applied Mathematics, 157 (2009), 464–475 | DOI | MR | Zbl

[20] K. Keating, A. Vince, “Isohedral Polyomino Tiling of the Plane”, Discrete and Computational Geometry, 21 (1999), 615–630 | DOI | MR | Zbl

[21] H. Fukuda, N. Mutoh, G. Nakamura, D. Schattschneider, “Enumeration of Polyominoes, Polyiamonds and Polyhexes for Isohedral Tilings with Rotational Symmetry”, LNCS, 4535, ed. H. Ito, Springer-Verlag, Berlin, Heidelberg, 2008, 68–78 | MR | Zbl

[22] H. Fukuda, N. Mutoh, G. Nakamura, D. Schattschneider, “A Method to Generate Polyominoes and Polyiamonds for Tilings with Rotational Symmetry”, Graphs and Combinatorics, 23 (2007), 259–267 | DOI | MR | Zbl

[23] D. Beauquier, M. Nivat, “On Translating One Polyomino To Tile the Plane”, Discrete Comput. Geom., 6 (1991), 575–592 | DOI | MR | Zbl

[24] N. Madras, G. Slade, The self-Avoiding Walk, Birkhäuser | MR