chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2024-25-1-138-154cheb-1682Research ArticleСтатьиArticleО числе изоэдральных полиминоOn the number of isohedral polyominoesШутовАнтон ВладимировичShutovAnton Vladimirovich

доктор физико-математических наук

doctor of physical and mathematical sciences

a1981@mail.ruМокроваАльбина АндреевнаMokrovaAlbina Andreevna

кандидат физико-математических наук

candidate of physical and mathematical sciences

albina.mokrova@yandex.ruВладимирский государственный университет им. Александра Григорьевича и Николая Григорьевича СтолетовыхРоссияVladimir State University named after Alexander and Nikolay StoletovsRussian Federation202424042024251138154Copyright © Шутов А.В., Мокрова А.А., 20242024Шутов А.В., Мокрова А.А.Shutov A.V., Mokrova A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/1682

Полимино представляет собой связную фигуру на плоскости, составленную из конечного числа единичных квадратов, примыкающих друг к другу по сторонам. Разбиение плоскости на полимино называется изоэдральным, если группа симметрий действует на нем транзитивно, то есть если для любых двух полимино разбиения существует глобальная симметрия разбиения, переводящая одно полимино во второе.В работе рассматривается задача о подсчете числа полимино площади 𝑛, порождающих изоэдральные разбиения плоскости. Показано, что число таких полимино не превосходит 𝐶(𝜀)𝑛^4(𝜔+𝜀)^𝑛, где 𝜔 - константа связности квадратной решетки Z^2. Известно, что 𝜔 < 2.7.Подобные оценки получены также в случае, когда фиксирован периметр, а не площадь полимино. Кроме того, аналогичная оценка справедлива и для числа самих изоэдральных разбиений плоскости при дополнительном условии регулярности разбиений.Ранее аналогичные результаты были получены в случае решетчатых разбиений плоскости на полимино, для так называемых 𝑝2-разбиений, а также для решетчатых разбиенийна центрально-симметричные полимино.Доказательство основано на критерии существования изоэдрального разбиения плоскости на полимино, полученного Лангерманом и Винслоу, а также на подсчете числа самонепересекающихся случайных блужданий на решетке Z2, как стандартных, так и обладающих заданной группой симметрии.В заключении кратко обсуждаются возможные направления дальнейших исследований и некоторые открытые проблемы.

A polyomino is a connected figure on a plane composed from a finite number of unit squares adjacent to each other on the sides. A tiling of a plane into polyominoes is called isohedral if the symmetry group acts transitively on it, that is, if for any two polyominoes of the tiling there is a global symmetry of the tiling that moves one polyomino into the second. The paper considers the problem of counting the number of polyominoes of area 𝑛 that generate isohedral tilings of the plane. It is shown that the number of such polyominoes does not exceed 𝐶(𝜀)𝑛^4(𝜔 + 𝜀)^𝑛, where 𝜔 is the connective constant of the square lattice Z^2. It is known that 𝜔 < 2.7. Similar estimates were also obtained in the case where the perimeter rather than the area of the polyomino is fixed. In addition, a similar estimate is valid for the number of isohedral tilings of the plane themselves under the additional condition of regularity of the tilings Previously, similar results were obtained in the case of lattice tilings of the plane intopolyominoes, for the so-called 𝑝2-splits, as well as for lattice tilings into centrally symmetric polyominoes.The proof is based on the criteria for the existence of an isohedral tiling of the plane into polyominoes obtained by Langerman and Winslow, as well as on counting the number of selfavoidingrandom walks on the lattice Z2, both standard and with a given symmetry group.In conclusion, possible directions for further research and some open problems are briefly discussed.

полиминоизоэдральные полиминоразбиения плоскостикритерии изоэдральности.polyominoesisohedral polyominoesplane tilingsisohedrality criteria.ReferencesGolomb S. W. Checker boards and polyominoes // American Mathematical Monthly. 1954. Vol. 61. P. 672–682.Golomb S. W. 1954, “Checker boards and polyominoes”, American Mathematical Monthly, vol. 61, pp. 672–682. (https://doi.org/10.2307/2307321)Голомб С.В. Полимино М.: Мир. 1975. 207 c.Golomb S. W. 1994, “Polyominoes, 2nd edition”, Princeton University Press, New Jercey, 196 p. (https://doi.org/10.1515/9780691215051)Gardner M. More about tiling the plane: the possibilities of polyominoes, polyiamonds, and polyhexes // Scientic American. 1975. P. 112–115.Gardner M. 1975, “More about tiling the plane: the possibilities of polyominoes, polyiamonds, and polyhexes”, Scientic American, pp 112–115. (https://doi.org/10.1038/scientificamerican0875-112)Rhoads G. C. Planar tilings by polyominoes, polyhexes, and polyiamonds // Journal of Computational and Applied Mathematics. 2005. Vol. 174. P. 329–353.Rhoads G. C. 2005, “Planar tilings by polyominoes, polyhexes, and polyiamonds” Journal of Computational and Applied Mathematics,vol. 174, pp. 329–353. (https://doi.org/10.1016/j.cam.2004.05.002)Rawsthorne D. Tiling complexity of small n-ominoes (n < 10) // Discrete Math. 1988. Vol. 70, no. 1. P. 71–75Rhoads G. C. 2003, “Planar Tilings and the Search for an Aperiodic Prototile”, PhD dissertation, Rutgers University.Rhoads G. C. Planar Tilings and the Search for an Aperiodic Prototile. PhD dissertation. Rutgers University. 2003.Rawsthorne D. 1988, “Tiling complexity of small n-ominoes (n < 10)”, Discrete Math., vol. 70, no. 1, pp. 71–75. (https://doi.org/10.1016/0012-365X(88)90081-7)Myers J. Polyomino, polyhex and polyiamond tiling. Available at: https://www.polyomino .org.uk/mathematics/polyform-tiling/Myers J. 2016, “Polyomino, polyhex and polyiamond tiling”, Available at: https://www.polyomino.org.uk/mathematics/polyform-tiling/Fontaine A., Martin G. Polymorphic polyominoes // Math. Mag. 1984. Vol. 57, no. 5. P. 275–283.Fontaine A. & Martin G. 1984, “Polymorphic polyominoes”, Math. Mag., vol. 57, no. 5, pp. 275–283.Kazuyuki A., Yoshinobu H. On the number of p4-tilings by an 𝑛-omino // Internat. J. Comput. Geom. Appl. 2018. Vol. 29, no. 1. P. 3–19.(https://doi.org/10.1080/0025570X.1984.11977126)Малеев А. В. Алгоритм и компьютерная программа перебора вариантов упаковок полимино в плоскости // Кристаллография. 2013. Т. 58. Вып. 5. С. 749–756.Kazuyuki A. & Yoshinobu H. 2018, “On the number of p4-tilings by an 𝑛-omino”, Internat. J. Comput. Geom. Appl., vol. 29, no. 1, pp. 3–19. (https://doi.org/10.1142/S0218195919400016)Fukuda H., Mutoh N., Nakamura G. Schattschneider D. A method to generate polyominoes and polyiamonds for tilings with rotational symmetry // Graphs and Combinatorics. 2007. Vol. 23, Supplement 1. P. 259–267.Maleev A. V. 2013, “Algorithm and computer-program search for variants of polyomino packings in plane”, Kristallografija, vol. 58, no. 5, pp. 749–756. (https://doi.org/10.7868/S0023476113040140)Fukuda H., Mutoh N., Nakamura G. Schattschneider D. Enumeration of polyominoes, polyiamonds and polyhexes for isohedral tilings with rotational symmetry // Computational Geometry and Graph Theory - International Conference. KyotoCGGT. Kyoto. Japan. June 11–15, 2007. Revised Selected Papers. Springer. P. 68–78.Fukuda H. & Mutoh N. & Nakamura G. & Schattschneider D. 2007, “A method to generate polyominoes and polyiamonds for tilings with rotational symmetry”, Graphs and Combinatorics, vol. 23, no. 1, pp. 259–267. (https://doi.org/10.1007/s00373-007-0719-y)Horiyama T., Samejima M. Enumeration of polyominoes for p4 tiling // Proc. 21st Canadian Conf. Computational Geometry. CCCG, 2009. P. 29–32.Fukuda H. & Mutoh N. & Nakamura G. & Schattschneider D. 2008, “Enumeration of polyominoes, polyiamonds and polyhexes for isohedral tilings with rotational symmetry”, Computational Geometry and Graph Theory - International Conference, KyotoCGGT 2007, Kyoto, Japan, June 11–15, 2007. Revised Selected Papers, Springer, pp. 68–78. (https://doi.org/10.1007/978-3-540-89550-3_7)Beauquier D., Nivat M. On translating one polyomino to tile the plane // Discrete Comput. Geom. 1991. Vol. 6, no. 6. P. 575–592.Horiyama T. & Samejima M. 2009, “Enumeration of polyominoes for p4 tiling”, Proc. 21st Canadian Conf. Computational Geometry (CCCG 2009), pp. 29–32.Brlek S., Provencal X. Fedou J.-M. On the tiling by translation problem // Discrete Applied Mathematics. 2009. Vol. 157, no. 3, P. 464–475.Beauquier D. & M. Nivat M. 1991, “On translating one polyomino to tile the plane”, Discrete Comput. Geom., vol. 6, no. 6, pp. 575–592. (https://doi.org/10.1007/BF02574705)Gambini I. Vuillon L. An algorothm for deciding if a polyomino tiles the plane by translations // RAIRO Theoretical Informatics and Applications. 2007. Vol. 41, no. 2. P. 147–155.Brlek S. & Provencal X & Fedou J.-M. 2009, “On the tiling by translation problem”, Discrete Applied Mathematics, vol. 157, no. 3, pp. 464–475. (https://doi.org/10.1016/j.dam.2008.05.026)Keating K., Vince A. Isohedral polyomino tiling of the plane // Discrete Comput. Geom. 1999. Vol. 21, no. 4. P. 615–630.Gambini I. & Vuillon L. 2007, “An algorothm for deciding if a polyomino tiles the plane by translations”, RAIRO Theoretical Informatics and Applications, vol. 41, no. 2, pp. 147–155. (https://doi.org/10.1051/ita: 2007012)Lanngerman S., Winslow A. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino // Proc. of 32nd International Symposium on Computational Geometry (SoCG 2016). 2016. P. 50:1–50:15.Keating K. & Vince A. 1999, “Isohedral polyomino tiling of the plane”, Discrete Comput. Geom., vol. 21, no. 4, pp. 615–630. (https://doi.org/10.1007/PL00009442)Brlek S., Frosini A., Rinaldi S. Vuillon L. Tilings by translation: enumeration by a rational language approach // The electronic journal of combinatorics. 2006. Vol. 13. P. 15.Lanngerman S. & Winslow A. 2016, “A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino”, Proc. of 32nd International Symposium on Computational Geometry (SoCG 2016), vol. 50, pp. 1–50. (https://doi.org/10.4230/LIPIcs.SoCG.2016.50)Малеев А. В., Шутов А. В. О числе трансляционных разбиений плоскости на полимино // Труды IX Всероссийской научной школы “Математические исследования в естественных науках”. Апатиты. 2013. С. 101–106.Brlek S. & Frosini A. & Rinaldi S. & Vuillon L. 2006, “Tilings by translation: enumeration by a rational language approach”, The electronic journal of combinatorics, vol. 13, p. 15. (https://doi.org/10.37236/1041)Шутов А. В., Коломейкина Е. В. Оценка числа решетчатых разбиений плоскости на полимино заданной площади // Моделирование и анализ информационных систем. 2013. Т. 20. Вып. 5. С. 148–157.Maleev A. V. & Shutov A. V. 2013, “On the number of translational plane tilings by polyomino”, Trudy IX Vserossiiskoi nauchnoi shkoly “Matematicheskie issledovaniya v estestvennyh naukah” (Proc. IX All-Russian scientfic school "Mathematical Research in Natural sciences Apatity, pp. 101–106.Шутов А. В., Коломейкина Е. В. Оценка числа решетчатых разбиений плоскости на центрально–симметричные полимино заданной площади // Моделирование и анализ информационных систем. 2015. Т. 22. Вып. 2. C. 295–303.Shutov A. V. & Kolomeykina E. V. 2013, “The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino”, Model. Anal. Inform. Sist., vol. 20, no. 5, pp. 148–157. (https://doi.org/10.18255/1818-1015-2013-5-148-157)Шутов А.В., Коломейкина Е.В. Оценка числа p2–разбиений плоскости на полимино заданной площади // Чебышевский сборник. 2016. Т.17. Вып. 3. С. 204–214.Shutov A. V. & Kolomeykina E. V. 2015, “The estimating of the number of lattice tilings of a plane by a given area centrosymmetrical polyomino”, Model. Anal. Inform. Sist., vol. 22, no. 2, pp. 295–303. (https://doi.org/10.18255/1818-1015-2015-2-295-303)Goodman-Strauss C. Can’t decide? undecide! // Notices of the American Mathematical Society. 2010. Vol. 57(3). P. 343–356.Shutov A. V. & Kolomeykina E. V. 2016, “The estimation of the number of p2-tilings of a plane by a given area polyomino”, Chebyshevskii Sbornik., vol. 17, no. 3, pp. 204–214. (https://doi.org/10.22405/2226-8383-2016-17-3-204-214)Hilbert D. Mathematical problems // Bulletin of the American Mathematical Society. 1902. Vol. 8(10). P. 437-479.Goodman-Strauss C. 2010, “Can’t decide? undecide!”, Notices of the American Mathematical Society, vol. 57, no. 3, pp. 343–356.Grunbaum B., Shephard G.C. The eighty-one types of isohedral tilings in the plane // Mathematical Proceedings of the Cambridge Philosophical Society. 1977. Vol. 82(2). P. 177–196.Hilbert D. 1902, “Mathematical problems”, Bulletin of the American Mathematical Society, vol. 8, no. 10, pp. 437-479. (https://doi.org/10.1090/S0002-9904-1902-00923-3)Heesch H., Kienzle O. Flachenschluss: System der Formen luckenlos aneinanderschliessender Flachteile. Springer. 1963.Grunbaum B. & Shephard G. C. 1977, “The eighty-one types of isohedral tilings in the plane”, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 82, no. 2, pp. 177–196.(https://doi.org/10.1017/S0305004100053810)Schattschneider D. Will it tile? try the Conway criterion! // Mathematics Monthly. 1980. Vol. 53(4). P. 224-233.Heesch H. & Kienzle O. 1963, “Flachenschluss: System der Formen luckenlos aneinanderschliessender Flachteile”, Springer.Bauerschmidt R., Duminil-Copin H., Goodman J., Slade G. “Lectures on selfavoiding walks”, Probability and Statistical Physics in Two and More Dimensions // Clay Mathematics Proceedings. 2010. Vol. 15. P. 395–476.Schattschneider D. 1980, “Will it tile? try the Conway criterion!”, Mathematics Monthly, vol. 53, no. 4, pp. 224-233. (https://doi.org/10.2307/2689617)SchattschneiderD. John Conway, Tilings, and Me! // Mathematical Intelligencer. 1921. Vol. 43(2). P. 124–129.Bauerschmidt R. & Duminil-Copin H. & Goodman J. & Slade G. 2010, “Lectures on selfavoiding walks”, Probability and Statistical Physics in Two and More Dimensions. Clay Mathematics Proceedings, vol. 15, pp. 395–476.Schattschneider D. 1921, “John Conway, Tilings, and Me!”, Mathematical Intelligencer, vol. 43, no. 2, pp. 124–129. (https://doi.org/10.1007/s00283-021-10062-0)Schattschneider D. 1921, “John Conway, Tilings, and Me!”, Mathematical Intelligencer, vol. 43, no. 2, pp. 124–129. (https://doi.org/10.1007/s00283-021-10062-0)

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