<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">cheb</journal-id><journal-title-group><journal-title xml:lang="ru">Чебышевский сборник</journal-title><trans-title-group xml:lang="en"><trans-title>Chebyshevskii Sbornik</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">2226-8383</issn><publisher><publisher-name>Tula State Lev Tolstoy  Pedagogical University</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.22405/2226-8383-2016-17-3-204-214</article-id><article-id custom-type="elpub" pub-id-type="custom">cheb-270</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Статьи</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>Article</subject></subj-group></article-categories><title-group><article-title>ОЦЕНКА ЧИСЛА Р2–РАЗБИЕНИЙ ПЛОСКОСТИ НА ПОЛИМИНО ЗАДАННОЙ ПЛОЩАДИ</article-title><trans-title-group xml:lang="en"><trans-title>THE ESTIMATION OF THE NUMBER OF P2–TILINGS OF A PLANE BY A GIVEN AREA POLYOMINO</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Шутов</surname><given-names>А. В.</given-names></name><name name-style="western" xml:lang="en"><surname>Shutov</surname><given-names>A. V.</given-names></name></name-alternatives><bio xml:lang="ru"><p>кандидат физико-математических наук, доцент, доцент кафедры управления и информатики в технических и экономических системах</p></bio><bio xml:lang="en"><p>Candidate of Physical and Mathematical Sciences, Associate Professor, Associate Professor of the Department of Management and Informatics in Technical and Economic Systems</p></bio><email xlink:type="simple">a1981@mail.ru</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Коломейкина</surname><given-names>Е. В.</given-names></name><name name-style="western" xml:lang="en"><surname>Kolomeykina</surname><given-names>E. V.</given-names></name></name-alternatives></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых</institution><country>Россия</country></aff><aff xml:lang="en"><institution>Vladimir State University named after Alexander G. and Nicholay G. Stoletovs</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2016</year></pub-date><pub-date pub-type="epub"><day>12</day><month>12</month><year>2016</year></pub-date><volume>17</volume><issue>3</issue><fpage>204</fpage><lpage>214</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Шутов А.В., Коломейкина Е.В., 2016</copyright-statement><copyright-year>2016</copyright-year><copyright-holder xml:lang="ru">Шутов А.В., Коломейкина Е.В.</copyright-holder><copyright-holder xml:lang="en">Shutov A.V., Kolomeykina E.V.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://www.chebsbornik.ru/jour/article/view/270">https://www.chebsbornik.ru/jour/article/view/270</self-uri><abstract><p>В работе рассматривается задача о числе \(p\)2--разбиений плоскости на полимино заданной площади. Полимино представляет собой связную фигуру на плоскости, составленную из конечного числа единичных квадратов, примыкающих друг к другу по сторонам. В настоящее время активно исследуются различные перичислительные комбинаторные задачи, связанные с полимино. Представляет интерес подсчет числа полимино определенных классов, а также подсчет числа разбиений конечных фигур или всей плоскости на полимино определенного типа. Разбиение называется \(p\)2--разбиением, если любую фигуру разбиения можно перевести в любую другую фигуру параллельным переносом или центральной симметрией, причем это преобразование переводит все разбиение в себя. \(p2\)-разбиения являются частным случаем правильных разбиений плоскости. Пусть \(t(n)\) -- число \(p2\)--разбиений плоскости на полимино площади \(n\), решетка периодов которых является подрешеткой решетки \(\mathbb{Z}^2\). Доказано, что справедливо неравенство \( C_12^n \leq t(n)\leq C_2n^4(2.68)^n\). При доказательстве нижней оценки использована явная конструкция, позволяющая построить требуемое число \(p2\)--разбиений плоскости. Доказательство верхней оценки основано на критерии Конвея существования \(p2\)--разбиений плоскости, а также на теории самонепересекающихся блужданий на квадратной решетке.Ранее аналогичные результаты были получены авторами в задаче подсчета числа решетчатых разбений плоскости на полимино заданной площади, а также в задаче подсчета числа решетчатых разбиений плоскости на центрально-симметричные полимино.</p></abstract><trans-abstract xml:lang="en"><p>We consider the problem about a number of \(p2\)--tilings of a plane by a given area polyominoes. A polyomino is a connected plane geometric figure formed by joining one or more 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 whole plane by polyominoes. The tiling is called \(p2\)--tiling, if each tile can be mapped to any other tile  by the translation or the central symmetry, and this transformation maps the whole tiling to itself. \(p2\)-tilings are special case of regular plane tilings. Let \(t(n)\) be a number of \(p2\)--tilings of a plane by a \(n\)-area polyomino such that the lattices of periods of these tilings are sublattices of \(\mathbb{Z}^2\). It is proved that following inequality is true: \( C_12^n \leq t(n)\leq C_2n^4(2.68)^n\). To prove the lower bound we use the exact construction of required tilings. The proof of the upper bound is based on the Conway criterion of the existence of \(p2\)--tilings of a plane. Also, the upper bound depends on the theory of self-avoiding walks on the square lattice. Earlier similar results were obtained by authors for the number of lattice tilings of a plane by a given area polyomino (it's more simple type of a plane tilings by polyomino), and for the number of lattice tilings of the plane by centrosimmetrical polyomino.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>разбиения</kwd><kwd>правильные разбиения</kwd><kwd>кристаллографические группы</kwd></kwd-group><kwd-group xml:lang="en"><kwd>tilings</kwd><kwd>regular tilings</kwd><kwd>crystallographic groups</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Ammann R., Grunbaum B., Shephard G. Aperiodic tiles // Discrete and Computational Geometry. 1991. Vol. 6, no. 1, P. 1–25.</mixed-citation><mixed-citation xml:lang="en">Ammann R. &amp; Grunbaum B. &amp; Shephard G. 1991, "Aperiodic tiles", Discrete and Computational Geometry, Vol. 6, no. 1, pp. 1–25. doi: 10.1007/BF02293033.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Barequet G., Rote G., Shalah M.</mixed-citation><mixed-citation xml:lang="en">Barequet G., Rote G. &amp; Shalah M. 2015, "</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Bousquet-Melou M. &amp; Brak R. 2009, "Exactly Solved Models", Polygons, Polyominoes and Polycubes, Springer, pp. 43–78. doi:10.1007/978-1-4020-9927-4.</mixed-citation><mixed-citation xml:lang="en">Bousquet-Melou M. &amp; Brak R. 2009, "Exactly Solved Models", Polygons, Polyominoes and Polycubes, Springer, pp. 43–78. doi:10.1007/978-1-4020-9927-4.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Brlek S., Frosini A., Rinaldi S. &amp; Vuillon L. 2006, "Tilings by translation: enumeration by a rational language approach", The electronic journal of combinatorics, Vol. 13, R15.</mixed-citation><mixed-citation xml:lang="en">Brlek S., Frosini A., Rinaldi S. &amp; Vuillon L. 2006, "Tilings by translation: enumeration by a rational language approach", The electronic journal of combinatorics, Vol. 13, R15.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Brlek S., Provencal X. &amp; Fedou J.-M. 2009, "On the tiling by translation problem", Discrete Applied Mathematics, Vol. 157, no. 3, pp. 464–475. doi:10.1016/j.dam.2008.05.026.</mixed-citation><mixed-citation xml:lang="en">Brlek S., Provencal X. &amp; Fedou J.-M. 2009, "On the tiling by translation problem", Discrete Applied Mathematics, Vol. 157, no. 3, pp. 464–475. doi:10.1016/j.dam.2008.05.026.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Fukuda H., Mutoh N., Nakamura G. &amp; Schattschneider D. 2007, "A method to generate polyominoes and polyiamonds for tilings with rotational symmetry", Graphs and Combinatorics, Vol. 23, Supplement 1, pp. 259–267. doi: 10.1007/s00373-007-0719-y.</mixed-citation><mixed-citation xml:lang="en">Fukuda H., Mutoh N., Nakamura G. &amp; Schattschneider D. 2007, "A method to generate polyominoes and polyiamonds for tilings with rotational symmetry", Graphs and Combinatorics, Vol. 23, Supplement 1, pp. 259–267. doi: 10.1007/s00373-007-0719-y.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Fukuda H., Mutoh N., Nakamura G. &amp; 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. doi:10.1007/978-3-540-89550-3_7.</mixed-citation><mixed-citation xml:lang="en">Fukuda H., Mutoh N., Nakamura G. &amp; 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. doi:10.1007/978-3-540-89550-3_7.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Gambini I. &amp; 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.</mixed-citation><mixed-citation xml:lang="en">Gambini I. &amp; 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.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Golomb S. W. 1954, "Checker boards and polyominoes", American Mathematical Monthly, Vol. 61, pp. 672–682. doi: 10.2307/2307321.</mixed-citation><mixed-citation xml:lang="en">Golomb S. W. 1954, "Checker boards and polyominoes", American Mathematical Monthly, Vol. 61, pp. 672–682. doi: 10.2307/2307321.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Jensen I. 2003, "Counting polyominoes: a parallel implementation for cluster computing", Computational Science – ICCS 2003 Proceedings, Part III, Springer, pp. 203–212.</mixed-citation><mixed-citation xml:lang="en">Jensen I. 2003, "Counting polyominoes: a parallel implementation for cluster computing", Computational Science – ICCS 2003 Proceedings, Part III, Springer, pp. 203–212.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Klarner D. 1967, "A cell growth problems", Cand. J. Math., Vol. 19, pp. 851–863. doi: 10.4153/CJM-1967-080-4.</mixed-citation><mixed-citation xml:lang="en">Klarner D. 1967, "A cell growth problems", Cand. J. Math., Vol. 19, pp. 851–863. doi: 10.4153/CJM-1967-080-4.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Klarner D. A. &amp; Rivest R.L. 1973, "A procedure for improving the upper bound for the number of n-ominoes", Canad. J. Math., Vol. 25, pp. 585–602. doi:/10.4153/CJM-1973-060-4.</mixed-citation><mixed-citation xml:lang="en">Klarner D. A. &amp; Rivest R.L. 1973, "A procedure for improving the upper bound for the number of n-ominoes", Canad. J. Math., Vol. 25, pp. 585–602. doi:/10.4153/CJM-1973-060-4.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Madras N. &amp; Slade G. 1996, The self-avoiding walk, Springer, 427 pp. doi:10.1007/978-1-4614-6025-1.</mixed-citation><mixed-citation xml:lang="en">Madras N. &amp; Slade G. 1996, The self-avoiding walk, Springer, 427 pp. doi:10.1007/978-1-4614-6025-1.</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">Myers J. 2016, "Polyomino, polyhex and polyiamond tiling", Available at: https://www.polyomino.org.uk/mathematics/polyform-tiling/</mixed-citation><mixed-citation xml:lang="en">Myers J. 2016, "Polyomino, polyhex and polyiamond tiling", Available at: https://www.polyomino.org.uk/mathematics/polyform-tiling/</mixed-citation></citation-alternatives></ref><ref id="cit15"><label>15</label><citation-alternatives><mixed-citation xml:lang="ru">Rhoads G. C. 2003, Planar Tilings and the Search for an Aperiodic Prototile, PhD dissertation, Rutgers University.</mixed-citation><mixed-citation xml:lang="en">Rhoads G. C. 2003, Planar Tilings and the Search for an Aperiodic Prototile, PhD dissertation, Rutgers University.</mixed-citation></citation-alternatives></ref><ref id="cit16"><label>16</label><citation-alternatives><mixed-citation xml:lang="ru">Rhoads G. C. 2005, "Planar tilings by polyominoes, polyhexes, and polyiamonds", Journal of Computational and Applied Mathematics, Vol. 174, no. 2, pp. 329–353. doi:10.1016/j.jcam.2004.05.002.</mixed-citation><mixed-citation xml:lang="en">Rhoads G. C. 2005, "Planar tilings by polyominoes, polyhexes, and polyiamonds", Journal of Computational and Applied Mathematics, Vol. 174, no. 2, pp. 329–353. doi:10.1016/j.jcam.2004.05.002.</mixed-citation></citation-alternatives></ref><ref id="cit17"><label>17</label><citation-alternatives><mixed-citation xml:lang="ru">Schattschneider D. 1980, "Will it tile? Try the Conway criterion!", Mathematics Magazine, Vol. 53, no. 4, pp. 224–233.</mixed-citation><mixed-citation xml:lang="en">Schattschneider D. 1980, "Will it tile? Try the Conway criterion!", Mathematics Magazine, Vol. 53, no. 4, pp. 224–233.</mixed-citation></citation-alternatives></ref><ref id="cit18"><label>18</label><citation-alternatives><mixed-citation xml:lang="ru">Gardner M. 1999, Mathematical puzzles and diversions, 2nd edition, Dover, 447 pp.</mixed-citation><mixed-citation xml:lang="en">Gardner M. 1999, Mathematical puzzles and diversions, 2nd edition, Dover, 447 pp.</mixed-citation></citation-alternatives></ref><ref id="cit19"><label>19</label><citation-alternatives><mixed-citation xml:lang="ru">Гарднер М. 1966, New mathematical diversions from Scientific American, Simon and Shuster, 496 pp.</mixed-citation><mixed-citation xml:lang="en">Гарднер М. 1966, New mathematical diversions from Scientific American, Simon and Shuster, 496 pp.</mixed-citation></citation-alternatives></ref><ref id="cit20"><label>20</label><citation-alternatives><mixed-citation xml:lang="ru">Gardner M. 1974, Mathematical games from Scientific American, Simon and Shuster, 456 pp.</mixed-citation><mixed-citation xml:lang="en">Gardner M. 1974, Mathematical games from Scientific American, Simon and Shuster, 456 pp.</mixed-citation></citation-alternatives></ref><ref id="cit21"><label>21</label><citation-alternatives><mixed-citation xml:lang="ru">Gardner M. 1988, Time travel and other mathematics bewilderments, Freeman and Co., New York, 341 pp.</mixed-citation><mixed-citation xml:lang="en">Gardner M. 1988, Time travel and other mathematics bewilderments, Freeman and Co., New York, 341 pp.</mixed-citation></citation-alternatives></ref><ref id="cit22"><label>22</label><citation-alternatives><mixed-citation xml:lang="ru">Golomb S. W. 1994, Polyominoes, 2nd edition, Princeton University Press, New Jercey. 196 pp.</mixed-citation><mixed-citation xml:lang="en">Golomb S. W. 1994, Polyominoes, 2nd edition, Princeton University Press, New Jercey. 196 pp.</mixed-citation></citation-alternatives></ref><ref id="cit23"><label>23</label><citation-alternatives><mixed-citation xml:lang="ru">Maleev A. V. 2013, "Algorithm and computer-program search for variants of polyomino packings in plane", Kristallografija, Vol. 58, no. 5, pp. 749–756. (Russian). translation in Crystallography Reports, 2015, Vol. 60, no. 6, pp. 986–992. doi:10.7868/S0023476113040140.</mixed-citation><mixed-citation xml:lang="en">Maleev A. V. 2013, "Algorithm and computer-program search for variants of polyomino packings in plane", Kristallografija, Vol. 58, no. 5, pp. 749–756. (Russian). translation in Crystallography Reports, 2015, Vol. 60, no. 6, pp. 986–992. doi:10.7868/S0023476113040140.</mixed-citation></citation-alternatives></ref><ref id="cit24"><label>24</label><citation-alternatives><mixed-citation xml:lang="ru">Maleev A. V. &amp; 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.</mixed-citation><mixed-citation xml:lang="en">Maleev A. V. &amp; 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.</mixed-citation></citation-alternatives></ref><ref id="cit25"><label>25</label><citation-alternatives><mixed-citation xml:lang="ru">Nesterenko Ju. V., Galochkin A. I. &amp; Shidlovskij A. B. 1984, Vvedenie v teoriju chisel [Introduction in number theory]. Izdatel’stvo Moskovskogo Universiteta, Moskow, 152 pp.</mixed-citation><mixed-citation xml:lang="en">Nesterenko Ju. V., Galochkin A. I. &amp; Shidlovskij A. B. 1984, Vvedenie v teoriju chisel [Introduction in number theory]. Izdatel’stvo Moskovskogo Universiteta, Moskow, 152 pp.</mixed-citation></citation-alternatives></ref><ref id="cit26"><label>26</label><citation-alternatives><mixed-citation xml:lang="ru">Shutov A. V. &amp; Kolomeykina E. V. 2014, "On the number of lattice tilings of a plane by a given area polyomino", Trudy IX Vserossiiskoi nauchnoi shkoly "Matematicheskie issledovaniya v estestvennyh naukah"(Proc. IX All-Russian scientfic school "Mathematical Research in Natural sciences"), Apatity, pp. 147–152.</mixed-citation><mixed-citation xml:lang="en">Shutov A. V. &amp; Kolomeykina E. V. 2014, "On the number of lattice tilings of a plane by a given area polyomino", Trudy IX Vserossiiskoi nauchnoi shkoly "Matematicheskie issledovaniya v estestvennyh naukah"(Proc. IX All-Russian scientfic school "Mathematical Research in Natural sciences"), Apatity, pp. 147–152.</mixed-citation></citation-alternatives></ref><ref id="cit27"><label>27</label><citation-alternatives><mixed-citation xml:lang="ru">Shutov A. V. &amp; Kolomeykina E. V. 2013, "The estimation of the number of lattice tilings of a plane by a given area polyomino ", Modelirovanie i Analiz Informacionnyh Sistem (Modeling and Analysis of Information Systems), Vol. 20, no. 5, pp. 148–157.</mixed-citation><mixed-citation xml:lang="en">Shutov A. V. &amp; Kolomeykina E. V. 2013, "The estimation of the number of lattice tilings of a plane by a given area polyomino ", Modelirovanie i Analiz Informacionnyh Sistem (Modeling and Analysis of Information Systems), Vol. 20, no. 5, pp. 148–157.</mixed-citation></citation-alternatives></ref><ref id="cit28"><label>28</label><citation-alternatives><mixed-citation xml:lang="ru">Shutov A. V. &amp; Kolomeykina E. V. 2015, "The estimating of the number of lattice tilings of a plane by a given area centrosymmetrical polyomino", Modelirovanie i Analiz Informacionnyh Sistem (Modeling and Analysis of Information Systems), Vol. 22, no. 2, pp. 295–303.</mixed-citation><mixed-citation xml:lang="en">Shutov A. V. &amp; Kolomeykina E. V. 2015, "The estimating of the number of lattice tilings of a plane by a given area centrosymmetrical polyomino", Modelirovanie i Analiz Informacionnyh Sistem (Modeling and Analysis of Information Systems), Vol. 22, no. 2, pp. 295–303.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
