[seqfan] Re: New interpretation of A001045 - Jacobsthal numbers?

[Maximilian Hasler]

>> "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.)

Maximilian

>> The result from a computer program was:
>> 1,3,5,11,21,43,85,171,341,683,1365,2731,5461,10923,21845,43691
>> 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/
>