Tiling with L's and squares

Chinn, Phyllism ; Grimaldi, Ralph ; Heubach, Silvia

Journal of integer sequences, Tome 10 (2007) no. 2

Résumé

We consider tilings of $2 \times n, 3 \times n$, and $4 \times n$ boards with $1 \times 1$ squares and L-shaped tiles covering an area of three square units, which can be used in four different orientations. For the $2 \times 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 \times n$ and $4 \times 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 \times k$ and $4 \times 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 \times 1$ squares in all the tilings of the $2 \times n$ and $3 \times n$ boards and determine which type of tile is dominant in the long run.

Détail

Keywords: tilings, trominoes, recurrence relations, generating functions