maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2013-5-148-157mais-179Research ArticleОригинальные статьиArticlesОценка числа решетчатых разбиений плоскости на полимино заданной площадиThe Estimation of the Number of Lattice Tilings of a Plane by a Given Area PolyominoШутовАнтон ВладимировичShutovA. V.

канд. физ.-мат. наук, доцент,

600024 Россия, г. Владимир, ул. Строителей, 11

канд. физ.-мат. наук, доцент,

Stroitelei str., 11, Vladimir, 600024, Russia

a1981@mail.ruКоломейкинаЕкатерина ВикторовнаKolomeykinaE. V.

канд. физ.-мат. наук, доцент,

105005 Pоссия, г. Москва, 2-ая Бауманская ул., 5

канд. физ.-мат. наук, доцент,

2-nd Bauman str., 5, Moscow, 105005, Russia

pihta2@rambler.ruВладимирский государственный университетРоссияVladimir State UniversityRussian FederationМосковский государственный технический университет им. Н.Э.БауманаРоссияMoscow State Technical UniversityRussian Federation201320102013205148157Copyright © Шутов А.В., Коломейкина Е.В., 20132013Шутов А.В., Коломейкина Е.В.Shutov A.V., Kolomeykina E.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/179

Рассматривается задача о числе решетчатых разбиений плоскости на полимино заданной площади. Полимино представляет собой связную фигуру на плоскости, составленную из конечного числа единичных квадратов, примыкающих друг к другу по сторонам. Разбиение называется решетчатым, если любую фигуру разбиения можно перевести в любую другую фигуру параллельным переносом, переводящим все разбиение в себя. Пусть T(n) – число решетчатых разбиений плоскости на полимино площади n, решетка периодов которых является подрешеткой решетки Z² . Доказано, что 2 n−3 + 2[ n−3 2 ] ≤ T(n) ≤ C(n + 1)3 (2.7)n+1. При доказательстве нижней оценки использована явная конструкция, позволяющая построить требуемое число решетчатых разбиений плоскости. Доказательство верхней оценки основано на одном критерии существования решетчатого разбиения плоскости на полимино, а также на теории самонепересекающихся блужданий на квадратной решетке. Также доказано, что почти все полимино, дающие решетчатые разбиения плоскости, имеют большой периметр.

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.

разбиенияполиминоtilingspolyominoРФФИReferencesГоломб С.В. Полимино. М.: Мир, 1975. (Golomb S.W. Polyominoes. 1996. 198 p. ISBN: 9780691024448)Голомб С.В. Полимино. М.: Мир, 1975. (Golomb S.W. Polyominoes. 1996. 198 p. ISBN: 9780691024448)Golomb S.W. Checkerboards and polyominoes // Amer. Math. Monthly. 1954. 61. P. 672–682.Golomb S.W. Checkerboards and polyominoes // Amer. Math. Monthly. 1954. 61. P. 672–682.Гарднер М. Математические головоломки и развлечения. 2-е изд. М.: Мир, 1999, 447 с. (Gardner M. Mathematical puzzles and diversions. The University of Chicago press, 1987. ISBN: 978-0226282534.)Гарднер М. Математические головоломки и развлечения. 2-е изд. М.: Мир, 1999, 447 с. (Gardner M. Mathematical puzzles and diversions. The University of Chicago press, 1987. ISBN: 978-0226282534.)Гарднер М. Математические досуги. М.: Мир, 1972. 496 с. (Gardner M. Mathematical Recreations: A Collection in Honor of Martin Gardner. Dover, 1998. ISBN 0-486-40089-1.)Гарднер М. Математические досуги. М.: Мир, 1972. 496 с. (Gardner M. Mathematical Recreations: A Collection in Honor of Martin Gardner. Dover, 1998. ISBN 0-486-40089-1.)Гарднер М. Математические новеллы. М.: Мир, 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.)Гарднер М. Математические новеллы. М.: Мир, 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.)Гарднер М. Путешествие во времени. М.: Мир, 1990. 341 с. (Gardner M. Time Travel and Other Mathematical Bewilderments. W.H. Freeman and Company, 1987. ISBN 0-7167-1925-8.)Гарднер М. Путешествие во времени. М.: Мир, 1990. 341 с. (Gardner M. Time Travel and Other Mathematical Bewilderments. W.H. Freeman and Company, 1987. ISBN 0-7167-1925-8.)Klarner D. A Cell growth problems // Cand. J. Math. 1967. 19. P. 851–863.Klarner D. A Cell growth problems // Cand. J. Math. 1967. 19. P. 851–863.Barequet G., Moffie M., Rib A., Rote G. Counting polyominoes on twisted cylinders // Integers. 2006. 6. A22.Barequet G., Moffie M., Rib A., Rote G. Counting polyominoes on twisted cylinders // Integers. 2006. 6. A22.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.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.Jensen I. Counting polyominoes: A parallel implementation for cluster computing // Lecture Notes in Computer Science. 2003. 2659. P. 203–212.Jensen I. Counting polyominoes: A parallel implementation for cluster computing // Lecture Notes in Computer Science. 2003. 2659. P. 203–212.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.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.Glenn C. Rhoads Planar tilings by polyominoes, polyhexes, and polyiamonds // Journal of Computational and Applied Mathematics. 2005. 174. P. 329–353.Glenn C. Rhoads Planar tilings by polyominoes, polyhexes, and polyiamonds // Journal of Computational and Applied Mathematics. 2005. 174. P. 329–353.Rhoads G. C. Planar Tilings and the Search for an Aperiodic Prototile: PhD dissertation, Rutgers University, 2003.Rhoads G. C. Planar Tilings and the Search for an Aperiodic Prototile: PhD dissertation, Rutgers University, 2003.Myers J. Polyomino, polyhex and polyiamond tiling. http://www.srcf.ucam.org/jsm28/tiling/Myers J. Polyomino, polyhex and polyiamond tiling. http://www.srcf.ucam.org/jsm28/tiling/Ammann R., Grunbaum B., Shephard G. Aperiodic tiles // Discrete and Computational Geometry. 1991. 6. P. 1–25.Ammann R., Grunbaum B., Shephard G. Aperiodic tiles // Discrete and Computational Geometry. 1991. 6. P. 1–25.Малеев А.В. Алгоритм и компьютерная программа перебора вариантов упаковок полимино в плоскости // Кристаллография. 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].)Малеев А.В. Алгоритм и компьютерная программа перебора вариантов упаковок полимино в плоскости // Кристаллография. 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].)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.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.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.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.Brlek S., Provencal X., Fedou J.-M. On the tiling by translation problem // Discrete Applied Mathematics. 2009. 157, P. 464–475.Brlek S., Provencal X., Fedou J.-M. On the tiling by translation problem // Discrete Applied Mathematics. 2009. 157, P. 464–475.Keating K., Vince A. Isohedral Polyomino Tiling of the Plane // Discrete and Computational Geometry. 1999. 21. P. 615–630.Keating K., Vince A. Isohedral Polyomino Tiling of the Plane // Discrete and Computational Geometry. 1999. 21. P. 615–630.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.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.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.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.Beauquier D., Nivat M. On Translating One Polyomino To Tile the Plane// Discrete Comput. Geom. 1991. V. 6. P. 575–592.Beauquier D., Nivat M. On Translating One Polyomino To Tile the Plane// Discrete Comput. Geom. 1991. V. 6. P. 575–592.Madras N., Slade G. The self-Avoiding Walk // Birkh¨auser. ISBN 978–0–8176–3891–7.Madras N., Slade G. The self-Avoiding Walk // Birkh¨auser. ISBN 978–0–8176–3891–7.

The authors declare that there are no conflicts of interest present.