О числе изоэдральных полимино
https://doi.org/10.22405/2226-8383-2024-25-1-138-154
Аннотация
Полимино представляет собой связную фигуру на плоскости, составленную из конечного числа единичных квадратов, примыкающих друг к другу по сторонам. Разбиение плоскости на полимино называется изоэдральным, если группа симметрий действует на нем транзитивно, то есть если для любых двух полимино разбиения существует глобальная симметрия разбиения, переводящая одно полимино во второе.
В работе рассматривается задача о подсчете числа полимино площади 𝑛, порождающих изоэдральные разбиения плоскости. Показано, что число таких полимино не превосходит 𝐶(𝜀)𝑛^4(𝜔+𝜀)^𝑛, где 𝜔 - константа связности квадратной решетки Z^2. Известно, что 𝜔 < 2.7.
Подобные оценки получены также в случае, когда фиксирован периметр, а не площадь полимино. Кроме того, аналогичная оценка справедлива и для числа самих изоэдральных разбиений плоскости при дополнительном условии регулярности разбиений.
Ранее аналогичные результаты были получены в случае решетчатых разбиений плоскости на полимино, для так называемых 𝑝2-разбиений, а также для решетчатых разбиений
на центрально-симметричные полимино.
Доказательство основано на критерии существования изоэдрального разбиения плоскости на полимино, полученного Лангерманом и Винслоу, а также на подсчете числа самонепересекающихся случайных блужданий на решетке Z2, как стандартных, так и обладающих заданной группой симметрии.
В заключении кратко обсуждаются возможные направления дальнейших исследований и некоторые открытые проблемы.
Об авторах
Антон Владимирович Шутов
Владимирский государственный университет им. Александра Григорьевича и Николая Григорьевича Столетовых
Россия
Россия
доктор физико-математических наук
Альбина Андреевна Мокрова
Владимирский государственный университет им. Александра Григорьевича и Николая Григорьевича Столетовых
Россия
Россия
кандидат физико-математических наук
Список литературы
1. Golomb S. W. Checker boards and polyominoes // American Mathematical Monthly. 1954. Vol. 61. P. 672–682.
2. Голомб С.В. Полимино М.: Мир. 1975. 207 c.
3. Gardner M. More about tiling the plane: the possibilities of polyominoes, polyiamonds, and polyhexes // Scientic American. 1975. P. 112–115.
4. Rhoads G. C. Planar tilings by polyominoes, polyhexes, and polyiamonds // Journal of Computational and Applied Mathematics. 2005. Vol. 174. P. 329–353.
5. Rawsthorne D. Tiling complexity of small n-ominoes (n < 10) // Discrete Math. 1988. Vol. 70, no. 1. P. 71–75
6. Rhoads G. C. Planar Tilings and the Search for an Aperiodic Prototile. PhD dissertation. Rutgers University. 2003.
7. Myers J. Polyomino, polyhex and polyiamond tiling. Available at: https://www.polyomino .org.uk/mathematics/polyform-tiling/
8. Fontaine A., Martin G. Polymorphic polyominoes // Math. Mag. 1984. Vol. 57, no. 5. P. 275–283.
9. 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.
10. Малеев А. В. Алгоритм и компьютерная программа перебора вариантов упаковок полимино в плоскости // Кристаллография. 2013. Т. 58. Вып. 5. С. 749–756.
11. 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.
12. 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.
13. Horiyama T., Samejima M. Enumeration of polyominoes for p4 tiling // Proc. 21st Canadian Conf. Computational Geometry. CCCG, 2009. P. 29–32.
14. Beauquier D., Nivat M. On translating one polyomino to tile the plane // Discrete Comput. Geom. 1991. Vol. 6, no. 6. P. 575–592.
15. Brlek S., Provencal X. Fedou J.-M. On the tiling by translation problem // Discrete Applied Mathematics. 2009. Vol. 157, no. 3, P. 464–475.
16. 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.
17. Keating K., Vince A. Isohedral polyomino tiling of the plane // Discrete Comput. Geom. 1999. Vol. 21, no. 4. P. 615–630.
18. 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.
19. 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.
20. Малеев А. В., Шутов А. В. О числе трансляционных разбиений плоскости на полимино // Труды IX Всероссийской научной школы “Математические исследования в естественных науках”. Апатиты. 2013. С. 101–106.
21. Шутов А. В., Коломейкина Е. В. Оценка числа решетчатых разбиений плоскости на полимино заданной площади // Моделирование и анализ информационных систем. 2013. Т. 20. Вып. 5. С. 148–157.
22. Шутов А. В., Коломейкина Е. В. Оценка числа решетчатых разбиений плоскости на центрально–симметричные полимино заданной площади // Моделирование и анализ информационных систем. 2015. Т. 22. Вып. 2. C. 295–303.
23. Шутов А.В., Коломейкина Е.В. Оценка числа p2–разбиений плоскости на полимино заданной площади // Чебышевский сборник. 2016. Т.17. Вып. 3. С. 204–214.
24. Goodman-Strauss C. Can’t decide? undecide! // Notices of the American Mathematical Society. 2010. Vol. 57(3). P. 343–356.
25. Hilbert D. Mathematical problems // Bulletin of the American Mathematical Society. 1902. Vol. 8(10). P. 437-479.
26. 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.
27. Heesch H., Kienzle O. Flachenschluss: System der Formen luckenlos aneinanderschliessender Flachteile. Springer. 1963.
28. Schattschneider D. Will it tile? try the Conway criterion! // Mathematics Monthly. 1980. Vol. 53(4). P. 224-233.
29. 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.
30. SchattschneiderD. John Conway, Tilings, and Me! // Mathematical Intelligencer. 1921. Vol. 43(2). P. 124–129.
Рецензия
Для цитирования:
Шутов А.В., Мокрова А.А. О числе изоэдральных полимино. Чебышевский сборник. 2024;25(1):138-154. https://doi.org/10.22405/2226-8383-2024-25-1-138-154
For citation:
Shutov A.V., Mokrova A.A. On the number of isohedral polyominoes. Chebyshevskii Sbornik. 2024;25(1):138-154. (In Russ.) https://doi.org/10.22405/2226-8383-2024-25-1-138-154
Просмотров:
269
Послать статью по эл. почте 