Journal of Combinatorics
Volume 6 (2015)
Enumerating tilings of rectangles by squares with recurrence relations
Pages: 339 – 351
Counting the number of ways to tile an $m \times n$ rectangle with squares of various sizes is a traditional combinatorial problem. In this paper, we demonstrate a simple variation of the transfer matrix method for constructing the recurrence relations satisfied by the solutions to these problems. This method also generalizes to similar problems that have not been previously considered, including three-dimensional “tilings.” We are able to give an upper bound on the minimal order of the recurrence satisfied for fixed $m$, as well as to prove that there does not exist a graph whose matchings form a one-to-one correspondence with such tilings.
recurrence relation, tilings, line graphs
2010 Mathematics Subject Classification
Primary 05B45. Secondary 52C20.
Published 4 June 2015