Journal of Combinatorics

Volume 6 (2015)

Number 3

Enumerating tilings of rectangles by squares with recurrence relations

Pages: 339 – 351



Daryl Deford (Department of Mathematics, Dartmouth College, Hanover, New Hampshire, U.S.A.)


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