Journal of Integer Sequences, Vol. 13 (2010), Article 10.6.5

Tilings, Compositions, and Generalizations

Ralph P. Grimaldi
Department of Mathematics
Rose-Hulman Institute of Technology
Terre Haute, Indiana 47803


For n ≥ 1, let an count the number of ways one can tile a 1 × n chessboard using 1 × 1 square tiles, which come in w colors, and 1 × 2 rectangular tiles, which come in t colors. The results for an generalize the Fibonacci numbers and provide generalizations of many of the properties satisfied by the Fibonacci and Lucas numbers. We count the total number of 1 × 1 square tiles and 1 × 2 rectangular tiles that occur among the an tilings of the 1 × n chessboard. Further, for these an tilings, we also determine: (i) the number of levels, where two consecutive tiles are of the same size; (ii) the number of rises, where a 1 × 1 square tile is followed by a 1 × 2 rectangular tile; and, (iii) the number of descents, where a 1 × 2 rectangular tile is followed by a 1 × 1 square tile. Wrapping the 1 × n chessboard around so that the nth square is followed by the first square, the numbers of 1 × 1 square tiles and 1 × 2 rectangular tiles, as well as the numbers of levels, rises, and descents, are then counted for these circular tilings.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000032 A000045 A000129 A001045.)

Received August 13 2009; revised version received June 15 2010. Published in Journal of Integer Sequences, June 16 2010.

Return to Journal of Integer Sequences home page