The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino
https://doi.org/10.18255/1818-1015-2013-5-148-157
Abstract
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.
About the Authors
A. V. Shutov
Vladimir State University
Russian Federation
Russian Federation
канд. физ.-мат. наук, доцент,
Stroitelei str., 11, Vladimir, 600024, Russia
E. V. Kolomeykina
Moscow State Technical University
Russian Federation
Russian Federation
канд. физ.-мат. наук, доцент,
2-nd Bauman str., 5, Moscow, 105005, Russia
References
1. Голомб С.В. Полимино. М.: Мир, 1975. (Golomb S.W. Polyominoes. 1996. 198 p. ISBN: 9780691024448)
2. Golomb S.W. Checkerboards and polyominoes // Amer. Math. Monthly. 1954. 61. P. 672–682.
3. Гарднер М. Математические головоломки и развлечения. 2-е изд. М.: Мир, 1999, 447 с. (Gardner M. Mathematical puzzles and diversions. The University of Chicago press, 1987. ISBN: 978-0226282534.)
4. Гарднер М. Математические досуги. М.: Мир, 1972. 496 с. (Gardner M. Mathematical Recreations: A Collection in Honor of Martin Gardner. Dover, 1998. ISBN 0-486-40089-1.)
5. Гарднер М. Математические новеллы. М.: Мир, 1974. 456 с. (Gardner M. Mathematical Carnival: A New Round-up of Tantalizers and Puzzles from «Scientific American». Knopf Publishing Group, 1975. ISBN 0-394-49406-7.)
6. Гарднер М. Путешествие во времени. М.: Мир, 1990. 341 с. (Gardner M. Time Travel and Other Mathematical Bewilderments. W.H. Freeman and Company, 1987. ISBN 0-7167-1925-8.)
7. Klarner D. A Cell growth problems // Cand. J. Math. 1967. 19. P. 851–863.
8. Barequet G., Moffie M., Rib A., Rote G. Counting polyominoes on twisted cylinders // Integers. 2006. 6. A22.
9. Klarner D.A., Rivest R.L. A procedure for improving the upper bound for the number of n-ominoes // Canad. J. Math. 1973. 25. P. 585–602.
10. Jensen I. Counting polyominoes: A parallel implementation for cluster computing // Lecture Notes in Computer Science. 2003. 2659. P. 203–212.
11. Bousquet-Melou M., Brak R. Exactly Solved Models // In Polygons, Polyominoes and Polycubes. / Ed. A. J. Guttman // Lecture Notes in Physics. Springer, 2009. P. 43–78.
12. Glenn C. Rhoads Planar tilings by polyominoes, polyhexes, and polyiamonds // Journal of Computational and Applied Mathematics. 2005. 174. P. 329–353.
13. Rhoads G. C. Planar Tilings and the Search for an Aperiodic Prototile: PhD dissertation, Rutgers University, 2003.
14. Myers J. Polyomino, polyhex and polyiamond tiling. http://www.srcf.ucam.org/jsm28/tiling/
15. Ammann R., Grunbaum B., Shephard G. Aperiodic tiles // Discrete and Computational Geometry. 1991. 6. P. 1–25.
16. Малеев А.В. Алгоритм и компьютерная программа перебора вариантов упаковок полимино в плоскости // Кристаллография. 2013. Т. 58, № 5. С. 749–756. ( Maleev A.V. Algorithm and Computer-Program Search for Variants of Polyomino Packings in Plane // Crystallography. 2013. V. 58, No 5. P. 749–756 [in Russian].)
17. Srecko Brlek, Andrea Frosini, Simone Rinaldi, Laurent Vuillon. Tilings by translation: enumeration by a rational language approach// The electronic journal of combinatorics. 2006. 13, R15.
18. Ian Gambini, Laurent Vuillon. An algorothm for deciding if a polyomino tiles the plane by translations // RAIRO – Theoretical Informatics and Applications. 2007. 41.2. P. 147–155.
19. Brlek S., Provencal X., Fedou J.-M. On the tiling by translation problem // Discrete Applied Mathematics. 2009. 157, P. 464–475.
20. Keating K., Vince A. Isohedral Polyomino Tiling of the Plane // Discrete and Computational Geometry. 1999. 21. P. 615–630.
21. Fukuda H., Mutoh N., Nakamura G., Schattschneider D. Enumeration of Polyominoes, Polyiamonds and Polyhexes for Isohedral Tilings with Rotational Symmetry // H. Ito et al. (Eds.): KyotoCGGT 2007, LNCS 4535, Springer-Verlag, Berlin, Heidelberg, 2008. P. 68–78.
22. Fukuda H., Mutoh N., Nakamura G., Schattschneider D. A Method to Generate Polyominoes and Polyiamonds for Tilings with Rotational Symmetry // Graphs and Combinatorics. 2007. 23. P. 259–267.
23. Beauquier D., Nivat M. On Translating One Polyomino To Tile the Plane// Discrete Comput. Geom. 1991. V. 6. P. 575–592.
24. Madras N., Slade G. The self-Avoiding Walk // Birkh¨auser. ISBN 978–0–8176–3891–7.
Review
For citations:
Shutov A.V., Kolomeykina E.V. The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino. Modeling and Analysis of Information Systems. 2013;20(5):148-157. (In Russ.) https://doi.org/10.18255/1818-1015-2013-5-148-157
Views:
857
Email this article 