[seqfan] Re: New interpretation of A001045 - Jacobsthal numbers?
deutsch at duke.poly.edu
Mon Nov 3 01:01:12 CET 2008
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.
> Dear Seqfans, This message just arrived. (I do not know
> the author.) Can anyone answer it?
> > >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:
> > 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/
More information about the SeqFan