Journal of Integer Sequences, Vol. 10 (2007), Article 07.2.8

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