Tiling with L's and Squares
Phyllis Chinn
Department of Mathematics
Humboldt State University
Arcata, CA 95521
USA
Ralph Grimaldi
Department of Mathematics
Rose-Hulman Institute of Technology
Terre Haute, IN 47803
USA
Silvia Heubach
Department of Mathematics
California State University, Los Angeles
Los Angeles, CA 90032
USA
Abstract:
We consider tilings of 2 × n, 3 × n,
and 4 × n
boards with 1 × 1 squares and L-shaped tiles covering an area of
three square units, which can be used in four different orientations.
For the 2 × n board, the recurrence relation for the number of
tilings is of order three and, unlike most third order recurrence
relations, can be solved exactly. For the 3 × n and
4 × n
board, we develop an algorithm that recursively creates the basic
blocks (tilings that cannot be split vertically into smaller
rectangular tilings) of size
3 × k and 4 × k from which
we obtain the generating function for the total number of tilings. We
also count the number of L-shaped tiles and 1 × 1 squares in all
the tilings of the 2 × n and 3 × n boards
and determine
which type of tile is dominant in the long run.
Full version: pdf,
dvi,
ps,
latex
(Concerned with sequences
A028859 and
A077917.)
Received April 21 2006;
revised versions received February 28 2007.
Published in Journal of Integer Sequences March 19 2007.
Return to
Journal of Integer Sequences home page