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

deutsch deutsch at duke.poly.edu
Mon Nov 3 01:01:12 CET 2008

```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/
>

```