maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2015-2-295-303mais-247Research ArticleОригинальные статьиArticlesОценка числа решетчатых разбиений плоскости на центрально-симметричные полимино заданной площадиThe Estimating of the Number of Lattice Tilings of a Plane by a Given Area Centrosymmetrical 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 Federation201520042015222295303Copyright © Шутов А.В., Коломейкина Е.В., 20152015Шутов А.В., Коломейкина Е.В.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/247

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

We study a problem about the number of lattice plane tilings by the given area centrosymmetrical polyominoes. A polyomino is a connected plane geomatric figure formed by joiining a finite number of unit squares edge to edge. At present, various combinatorial enumeration problems connected to the polyomino are actively studied. There are some interesting problems on enuneration of various classes of polyominoes and enumeration of tilings of finite regions or a plane by polyominoes. In particular, the tiling is a lattice tiling if each tile can be mapped to any other tile by a translation which maps the whole tiling to itself. Earlier we proved that, for the number T(n) of a lattice plane tilings by polyominoes of an area n, holds the inequalities 2n−3 + 2[ n−3 2 ] ≤ T(n) ≤ C(n + 1)3 (2, 7)n+1 . In the present work we prove a similar estimate for the number of lattice tilings with an additional central symmetry. Let Tc(n) be a number of lattice plane tilings by a given area centrosymmetrical polyominoes such that its translation lattice is a sublattice of Z 2 . It is proved that C1( √ 2)n ≤ Tc(n) ≤ C2n 2 ( √ 2.68)n . 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 polyominoes, and on the theory of self-avoiding walks on a square lattice.

разбиенияполиминоtilingspolyominoРФФИReferencesGolomb S.W., “Checkerboards and polyominoes”, Amer. Math. Monthly, 61 (1954), 672–682.Golomb S.W., “Checkerboards and polyominoes”, Amer. Math. Monthly, 61 (1954), 672–682.Guttman A. J., Polygons, polyominoes and polycubes, Springer, 2009.Guttman A. J., Polygons, polyominoes and polycubes, Springer, 2009.Гарднер М., Путешествие во времени, Мир, М., 1990, 341 с.; Gardner M., Time Travel and Other Mathematical Bewilderments, 1988.Гарднер М., Путешествие во времени, Мир, М., 1990, 341 с.; Gardner M., Time Travel and Other Mathematical Bewilderments, 1988.Golomb S.W., “Tiling with sets of polyominoes”, Journal of Combinatorial Theory, 9 (1970), 60–71.Golomb S.W., “Tiling with sets of polyominoes”, Journal of Combinatorial Theory, 9 (1970), 60–71.Ammann R., Grunbaum B., Shephard G., “Aperiodic tiles”, Discrete and Computational Geometry, 1991, № 6, 1–25.Ammann R., Grunbaum B., Shephard G., “Aperiodic tiles”, Discrete and Computational Geometry, 1991, № 6, 1–25.Brlek S., Provencal X., Fedou J.-M., “On the tiling by translation problem”, Discrete Applied Mathematics, 157 (2009), 464–475.Brlek S., Provencal X., Fedou J.-M., “On the tiling by translation problem”, Discrete Applied Mathematics, 157 (2009), 464–475.Wijshoff H. A. G., van Leeuwen J., “Arbitrary versus Periodic Storage Schemes and Tesselations of the Plane Using One Type of Polyomino”, Information and control, 62 (1984), 1–25.Wijshoff H. A. G., van Leeuwen J., “Arbitrary versus Periodic Storage Schemes and Tesselations of the Plane Using One Type of Polyomino”, Information and control, 62 (1984), 1–25.Rhoads G. C., “Planar tilings by polyominoes, polyhexes, and polyiamonds”, Journal of Computational and Applied Mathematics, 174 (2005), 329–353.Rhoads G. C., “Planar tilings by polyominoes, polyhexes, and polyiamonds”, Journal of Computational and Applied Mathematics, 174 (2005), 329–353.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/.Голомб С., Полимино, Мир, 1975; Golomb S.W., Polyominoes, 1975.Голомб С., Полимино, Мир, 1975; Golomb S.W., Polyominoes, 1975.Fukuda H., Mutoh N., Nakamura G., Schattschneider D., “A Method to Generate Polyominoes and Polyiamonds for Tilings with Rotational Symmetry”, Graphs and Combinatorics, 23:1 (June 2007), 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, 23:1 (June 2007), 259–267.Fukuda H., Mutoh N., Nakamura G., Schattschneider D., “Enumeration of Polyominoes, Polyiamonds and Polyhexes for Isohedral Tilings with Rotational Symmetry”, Lecture Notes in Computer Science, 4535, 2008, 68–78.Fukuda H., Mutoh N., Nakamura G., Schattschneider D., “Enumeration of Polyominoes, Polyiamonds and Polyhexes for Isohedral Tilings with Rotational Symmetry”, Lecture Notes in Computer Science, 4535, 2008, 68–78.Fukuda H., Kanomata Ch., Mutoh N., Nakamura G., Schattschneider D., “Polyominoes and Polyiamonds as Fundamental Domains of Isohedral Tilings with Rotational Symmetry”, Symmetry, 3:4 (2011), 828.Fukuda H., Kanomata Ch., Mutoh N., Nakamura G., Schattschneider D., “Polyominoes and Polyiamonds as Fundamental Domains of Isohedral Tilings with Rotational Symmetry”, Symmetry, 3:4 (2011), 828.Horiyama T., Samejima M., “Enumeration of Polyominoes for p4 Tiling”, IEICE Tech.Rep. COMP2009-17, 109:54 (2009), 51–55.Horiyama T., Samejima M., “Enumeration of Polyominoes for p4 Tiling”, IEICE Tech.Rep. COMP2009-17, 109:54 (2009), 51–55.Малеев А. В., “Алгоритм и компьютерная программа перебора вариантов упаковок полимино в плоскости”, Кристаллография, 58:5 (2013), 749–756; English transl.: Maleev A. V., “Algorithm and Computer-program Search for Variants of Polyomino Packings in Plane”, Crystallography reports, 58:5 (2013), 760–767.Малеев А. В., “Алгоритм и компьютерная программа перебора вариантов упаковок полимино в плоскости”, Кристаллография, 58:5 (2013), 749–756; English transl.: Maleev A. V., “Algorithm and Computer-program Search for Variants of Polyomino Packings in Plane”, Crystallography reports, 58:5 (2013), 760–767.Малеев А. В., Шутов А. В., “О числе трансляционных разбиений плоскости на полимино”, Математические исследования в естественных науках: Труды IX Всероссийской научной школы, Апатиты: K & M, 2013, 101–106; [Maleev A. V., Shutov A. V., “O chisle translyatsionnykh razbieniy ploskosti na polimino”, Matematicheskie issledovaniya v estestvennykh naukakh: Trudy IX Vserossiyskoy nauchnoy shkoly, Apatity: K & M, 2013, 101–106, (in Russian).]Малеев А. В., Шутов А. В., “О числе трансляционных разбиений плоскости на полимино”, Математические исследования в естественных науках: Труды IX Всероссийской научной школы, Апатиты: K & M, 2013, 101–106; [Maleev A. V., Shutov A. V., “O chisle translyatsionnykh razbieniy ploskosti na polimino”, Matematicheskie issledovaniya v estestvennykh naukakh: Trudy IX Vserossiyskoy nauchnoy shkoly, Apatity: K & M, 2013, 101–106, (in Russian).]Brlek S., Frosini A., Rinaldi S., Vuillon L., “Tilings by translation: enumeration by a rational language approach”, R15, The electronic journal of combinatorics, 13 (2006).Brlek S., Frosini A., Rinaldi S., Vuillon L., “Tilings by translation: enumeration by a rational language approach”, R15, The electronic journal of combinatorics, 13 (2006).Beauquier D., Nivat M., “On Translating One Polyomino To Tile the Plane”, Discrete Comput. Geom., 6 (1991), 575—592.Beauquier D., Nivat M., “On Translating One Polyomino To Tile the Plane”, Discrete Comput. Geom., 6 (1991), 575—592.Шутов А. В., Коломейкина Е. В., “Оценка числа решетчатых разбиений плоскости на полимино заданной площади”, Моделирование и анализ информационных систем, 20:5 (2013), 148–157; [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, 20:5 (2013), 148–157, (in Russian).]Шутов А. В., Коломейкина Е. В., “Оценка числа решетчатых разбиений плоскости на полимино заданной площади”, Моделирование и анализ информационных систем, 20:5 (2013), 148–157; [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, 20:5 (2013), 148–157, (in Russian).]Gambini I., Vuillon L., “An algorothm for deciding if a polyomino tiles the plane by translations”, RAIRO – Theoretical Informatics and Applications 41.2, 2007, 147–155.Gambini I., Vuillon L., “An algorothm for deciding if a polyomino tiles the plane by translations”, RAIRO – Theoretical Informatics and Applications 41.2, 2007, 147–155.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, 15 (2010), 395–476.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, 15 (2010), 395–476.

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