Tiling with L's and Squares
Silvia Heubach · CSUN ScholarWorks (California State University, Northridge) · 2007
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.