Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.2

On Counting the Number of Tilings of a Rectangle with Squares of Size 1 and 2

Johan Nilsson
LIPN Université Paris 13
93430 Villetaneuse


We consider tilings of a rectangle of size n × k with square tiles of size 1 × 1 and 2 × 2. We present a method to calculate the number of such tilings via matrix multiplication, where we optimize the number of multiplications needed and reduce the space required for the matrix multiplication by dynamically generating the matrices involved.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000108 A001850 A005840 A006318 A008288.)

Received April 20 2016; revised version received December 1 2016. Published in Journal of Integer Sequences, December 27 2016.

Return to Journal of Integer Sequences home page