Enumerating tilings of rectangles by squares with recurrence relations

DOI10.4310/JOC.2015.V6.N3.A5MaRDI QIDQ746833zbMATH OpenOpenAlexFDO

Publication date 20 October 2015

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4310/joc.2015.v6.n3.a5

line graphs recurrence relation tilings of rectangle with squares transfer matrix method

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of tessellation and tiling problems (05B45) Graph operations (line graphs, products, etc.) (05C76) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Review text

The following problem is under consideration. Given an \(m \times n\) rectangular board and square tiles of various fixed dimensions, in how many different ways can the board be tiled? The transfer matrix method by \textit{S. Heubach} [Congr. Numerantium 140, 43--64 (1999; Zbl 0960.05035)] is based on constructing recurrence relations for sequences formed when \(m\) is fixed and \(n\) varies. However, the complexity grows significantly as the fixed number of rows grows. In the paper under review, the author proposes a variation of the transfer matrix method that allows to generate recurrence relations for a wider class of problems. In particular, the method is applied to the three-dimensional analogue of this problem, tiling \(m \times n \times k\) rectangular prism with cubes of fixed dimensions. The author gives an explicit upper bound on the order of recurrence for a tiling problem with \(1 \times 1\) and \(2 \times 2\) squares for fixed number of rows. He also proves that there does not exist a graph whose matchings have a one-to-one correspondence with such tilings.

Recommendations

Cited in

(12)

Describes a project that uses

Uses Software

OEIS

This page was built for publication: Enumerating tilings of rectangles by squares with recurrence relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q746833)