tiling a 2xn checkerboard with square tetrominoes and dominoes

Jonathan Post jvospost3 at gmail.com
Sun Feb 18 04:06:47 CET 2007


Dear Joshua Zucker,

Thank you for responding so quickly and clearly.

Yes, I like your comment on   A001045  Jacobsthal sequence: a(n) =
a(n-1) + 2a(n-2).
"Number of ways to tile a 3 X (n-1) rectangle with 1 X 1 and 2 X 2
square tiles. "

I drew my 2xn rectangles long-way up (Maybe as nx3, ambiguous).  So
I'll avoid confusing "horizontal" and vertical hereinbelow.

2x3: we have the 3 tilings into dominoes, plus two with a square
tetromino and a domino, the square being at one end or the other, so
a(2x3) = 3+2 = 5.

2x4: we have the 5 tilings into dominoes, plus 5 with a square
tetromino and 2 dominoes, with the square at either end, or in the
middle and, if the square's at an end, the 2 dominoes either both
horizontal or both vertical, so a(2x4) = 5+5 =10.

2x5: we have the 8 tilings into dominoes, plus 5 with a square
tetromino and a 2x3 in either of 3 ways (square at one end or the
other); plus the square in either of 2 middle places and a domino at
one end and a 2x2 in either of 2 ways at the other end; plus 3 ways
with 2 squares and one domino, the one domino at either end or between
the 2 squares; so a(2x5) = 8 + 13 = 21.

2x6: shall I continue, or there enough here to either find my error,
or find an ambiguity?

Better clear this up before I begin explaining my enumeration of 3xn
boards tiled with dominoes, square tetrominoes, and square nonominoes.





More information about the SeqFan mailing list