tiling a 2xn checkerboard with square tetrominoes and dominoes

[Joshua Zucker]

I'm confused.
Isn't it true that for your counting, let's say there are f(n) ways to
tile a 2xn board, then
f(n) = f(n-1) + 2*f(n-2),
where the f(n-1) corresponds to ending with a domino oriented "vertically"
and the 2*f(n-2) is from ending with the option of a tetromino OR a
pair of dominoes oriented "horizontally"?

If that's so, then with f(1) = 1 and f(2) = 3, ... and f(0) = 0 I
suppose ... well, I don't agree with your terms, so maybe I'm
misinterpreting your sequence or miscomputing mine.  I have
3,5,11,21,43,85 vs your 3,5,10,21,39,85.  In fact I have
  http://www.research.att.com/~njas/sequences/A001045
of course.

--Joshua Zucker


On 2/17/07, Jonathan Post <jvospost3 at gmail.com> wrote:
> 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.
>