Preview

Моделирование и анализ информационных систем

Расширенный поиск

Оценка числа решетчатых разбиений плоскости на полимино заданной площади

https://doi.org/10.18255/1818-1015-2013-5-148-157

Полный текст:

Аннотация

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

Ключевые слова


Об авторах

Антон Владимирович Шутов
Владимирский государственный университет
Россия

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

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



Екатерина Викторовна Коломейкина
Московский государственный технический университет им. Н.Э.Баумана
Россия

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

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



Список литературы

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.


Для цитирования:


Шутов А.В., Коломейкина Е.В. Оценка числа решетчатых разбиений плоскости на полимино заданной площади. Моделирование и анализ информационных систем. 2013;20(5):148-157. https://doi.org/10.18255/1818-1015-2013-5-148-157

For citation:


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

Просмотров: 338


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)