Enumerating tilings of rectangles by squares with recurrence relations

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.

Keywords

recurrence relation, tilings, line graphs

2010 Mathematics Subject Classification

Primary 05B45. Secondary 52C20.

Full Text (PDF format)

Published 4 June 2015