RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Model. Anal. Inform. Sist., 2015, Volume 22, Number 2, Pages 295–303 (Mi mais442)  

This article is cited in 1 scientific paper (total in 1 paper)

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

A. V. Shutova, E. V. Kolomeykinab

a Vladimir State University, Stroitelei str., 11, Vladimir, 600024, Russia
b Moscow State Technical University, 2-nd Bauman str., 5, Moscow, 105005, Russia

Abstract: 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.

Keywords: tilings, polyomino.

Full text: PDF file (485 kB)
References: PDF file   HTML file

Bibliographic databases:
UDC: 514.174.5
Received: 05.10.2014

Citation: A. V. Shutov, E. V. Kolomeykina, “The estimating of the number of lattice tilings of a plane by a given area centrosymmetrical polyomino”, Model. Anal. Inform. Sist., 22:2 (2015), 295–303

Citation in format AMSBIB
\Bibitem{ShuKol15}
\by A.~V.~Shutov, E.~V.~Kolomeykina
\paper The estimating of the number of lattice tilings of a plane by a given area centrosymmetrical polyomino
\jour Model. Anal. Inform. Sist.
\yr 2015
\vol 22
\issue 2
\pages 295--303
\mathnet{http://mi.mathnet.ru/mais442}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3417828}
\elib{http://elibrary.ru/item.asp?id=23405837}


Linking options:
  • http://mi.mathnet.ru/eng/mais442
  • http://mi.mathnet.ru/eng/mais/v22/i2/p295

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. V. Shutov, E. V. Kolomeikina, “Otsenka chisla $p2$–razbienii ploskosti na polimino zadannoi ploschadi”, Chebyshevskii sb., 17:3 (2016), 204–214  mathnet  mathscinet  elib
  • Моделирование и анализ информационных систем
    Number of views:
    This page:193
    Full text:46
    References:28

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020