[seqfan] Re: New interpretation of A001045 - Jacobsthal numbers?
maximilian.hasler at gmail.com
Sun Nov 2 18:25:29 CET 2008
>> "How many ways are there to tile a 2 x N rectangle
>> using 1x2 dominoes and 2x2 squares ?"
let a(N) be that number. Clearly a(1)=1 and a(2)=3.
Moreover we have a(N+1) = a(N) + a(N-1)*2,
where the first term arises from adding a 1x2 domino to the 2xN tiling,
and the second term arises from adding either a square, or 2 1x2
dominoes in "longitudinal" direction.
(Or otherwise said, a 2xN tiling has either its last piece being a
domino in "transverse" direction,
in which case removing it yields a 2x(N-1) tiling, or the last piece
is a square or 2 dominoes in longitudinal direction, in which case
removal will yield an N-2 tiling.)
Thus we have the recurrent equation defining the Jacobstal sequence,
and since we start with 1,3,... it is the same sequence (with index
shifted by one,
a(n) = A001045(n+1), n>0 ; we might add a(0)=1 considering the empty
tiling as the only possibility of tilng the 2x0 rectangle.)
>> The result from a computer program was:
>> which is http://www.research.att.com/~njas/sequences/A001045
>> the Jacobsthal numbers.
>> On that page it says
>> Number of ways to tile a 3 X (n-1) rectangle with 1 X 1 and 2 X 2 square tiles.
>> which is a similar problem.
>> Considering the basic nature of this problem
>> and the number of other applications of this sequence,
>> it would be quite a surprise if this were a new result,
>> but after a fairly extensive search on Google, I could
>> not find it anywhere.
>> Any comments ?
> (end - there was no signature)
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan