The estimating of the number of lattice tilings of a plane by a given area centrosymmetrical polyomino

A. V. Shutov ; E. V. Kolomeykina

Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 2, pp. 295-303.

Résumé

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 $2^{n-3}+2^{[\frac{n-3}{2}]}\leq T(n)\leq 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 $T_c(n)$ be a number of lattice plane tilings by a given area centrosymmetrical polyominoes such that its translation lattice is a sublattice of $\mathbb{Z}^2$. It is proved that $C_1(\sqrt 2)^n\leq T_c(n) \leq C_2n^2(\sqrt{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.

Détail

Keywords: tilings, polyomino.

Bibliographie

[1] Golomb S. W., “Checkerboards and polyominoes”, Amer. Math. Monthly, 61 (1954), 672–682 | MR

[2] Guttman A. J., Polygons, polyominoes and polycubes, Springer, 2009 | MR | Zbl

[3] Gardner M., Time Travel and Other Mathematical Bewilderments, W. H. Freeman, New York, 1988 | MR | MR | Zbl

[4] Golomb S. W., “Tiling with sets of polyominoes”, Journal of Combinatorial Theory, 9 (1970), 60–71 | DOI | MR | Zbl

[5] Ammann R., Grunbaum B., Shephard G., “Aperiodic tiles”, Discrete and Computational Geometry, 1991, no. 6, 1–25 | MR

[6] Brlek S., Provencal X., Fedou J.-M., “On the tiling by translation problem”, Discrete Applied Mathematics, 157 (2009), 464–475 | DOI | MR | Zbl

[7] 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 | DOI | MR | Zbl

[8] Rhoads G. C., “Planar tilings by polyominoes, polyhexes, and polyiamonds”, Journal of Computational and Applied Mathematics, 174 (2005), 329–353 | DOI | MR | Zbl

[9] Myers J., Polyomino, polyhex and polyiamond tiling, http://www.srcf.ucam.org/ ̃ jsm28/tiling/

[10] Golomb S. W., Polyominoes, 1975

[11] 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 | DOI | MR | Zbl

[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, Lecture Notes in Computer Science, 4535, 2008, 68–78 | MR | Zbl

[13] 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 | DOI | MR

[14] Horiyama T., Samejima M., “Enumeration of Polyominoes for p4 Tiling”, Proceedings of the 21st Annual Canadian Conference on Computational Geometry (Vancouver, British Columbia, Canada, August 17–19, 2009), 29–32; IEICE Tech. Rep., 109:54 (2009), COMP2009-17, 51–55

[15] Maleev A. V., “Algorithm and Computer-program Search for Variants of Polyomino Packings in Plane”, Crystallography reports, 58:5 (2013), 760–767 | DOI | DOI

[16] Maleev A. V., Shutov A. V., “O chisle translyatsionnykh razbieniy ploskosti na polimino”, Matematicheskie issledovaniya v estestvennykh naukakh, Trudy IX Vserossiyskoy nauchnoy shkoly, K M, Apatity, 2013, 101–106 (in Russian)

[17] Brlek S., Frosini A., Rinaldi S., Vuillon L., “Tilings by translation: enumeration by a rational language approach”, The electronic journal of combinatorics, 13 (2006), R15 | MR | Zbl

[18] Beauquier D., Nivat M., “On Translating One Polyomino To Tile the Plane”, Discrete Comput. Geom., 6 (1991), 575–-592 | DOI | MR | Zbl

[19] 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] Gambini I., Vuillon L., “An algorothm for deciding if a polyomino tiles the plane by translations”, Theoretical Informatics and Applications, 41:2 (2007), 147–155 | MR | Zbl

[21] Bauerschmidt R., Duminil-Copin H., Goodman J., Slade G., “Lectures on self-avoiding walks”, Probability and Statistical Physics in Two and More Dimensions, Clay Mathematics Proceedings, 15, Amer. Math. Soc., 2010, 395–476 | MR