tiling a 2xn checkerboard with square tetrominoes and dominoes

Jonathan Post jvospost3 at gmail.com
Sat Feb 17 23:44:33 CET 2007

It is well-known that the Fibonacci number F(n+1) gives the number of
ways for 2x1 dominoes  to cover a 2xn checkerboard [Dickau].




See also Graham, Knuth, and Patashnik, Concrete Mathematics: A
Foundation for Computer Science, Addison-Wesley, 1994.

Now, suppose that we enumerate tilings of a  2xn checkerboard with
square tetrominoes and dominoes?  It can be written as F(n+1) + number
of tilings of a  2x(n-2) checkerboard with 1 square tetromino and
dominoes +  number of tilings of a  2x(n-4) checkerboard with 2 square
tetrominoes and dominoes + ...

This can be written more neatly in terms of a recursion with
partitions of n into 1s and 2s  (isn't that Tribonacci numbers?) where
each partition of 2 corresponds to a square tetromino.

So the number of tilings of 2xn checkerboard with square tetrominoes
and dominoes seems to begin:

for n = 2, 3, 4, 5, ... a(n) = 3, 5, 10, 21, 39, 85, ...

Would someone like to give the formula I waved my hands at above, more
carefully, and verify and/or extend the sequence?

My wife and I celebrated our 21st wedding anniversary on 14 Feb 2007.
21 as a Fibonacci number made me think of this little problem.

More information about the SeqFan mailing list