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

[deutsch]

Dear Neil,

Proof is very simple. The basic tilings are 
1 x 2 domino vertically;
2 x 2 square;
two horizontal 1 x 2 dominos.

By basic I mean that every tiling is a concatenation 
of these tilings. The g.f. of the basic tilings is 
g=x + x^2 + x^2 = x + 2x^2.
Then the g.f. of all tilings is 
G = 1/(1-g)=1/(1-x-2x^2).
This leads to the given sequence. 
Emeric  

> 
> Dear Seqfans,   This message just arrived. (I do not know
> the author.) Can anyone answer it?
> Neil
> 
> 
> > >From toby at gottfriedville.net Sat Nov  1 20:32:17 2008
> > Delivered-To: njas at research.att.com
> > From: <toby at gottfriedville.net>
> > To: <njas at research.att.com>, <ed at mathpuzzle.com>
> > Subject: Cannot find this particular result anywhere
> > (A001045 - Jacobsthal numbers) Date: Sat, 1 Nov 2008
> > 17:32:52 -0700 
> > Someone on Yahoo Answers posed the question
> > 
> > "How many ways are there to tile a 2 x N rectangle
> >     using 1x2 dominoes and 2x2 squares ?"
> > 
> > The result from a computer program was:
> >
> 1,3,5,11,21,43,85,171,341,683,1365,2731,5461,10923,21845,4
> > 3691 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/
>