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].
http://mathworld.wolfram.com/FibonacciNumber.html
see:
http://www.prairienet.org/~pops/fibboard.html
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