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

[Richard Mathar]

njas> Date: Sun, 2 Nov 2008 11:41:48 -0500
njas> From: "N. J. A. Sloane" <njas at research.att.com>
njas> To: seqfan at seqfan.eu
njas> Cc: njas at research.att.com
njas> Subject: [seqfan]  New interpretation of A001045 - Jacobsthal numbers?
njas> 
njas> Dear Seqfans,   This message just arrived. (I do not know the author.)
njas> Can anyone answer it?
njas> Neil
njas> 
njas> t> >From toby at gottfriedville.net Sat Nov  1 20:32:17 2008
njas> t> Delivered-To: njas at research.att.com
njas> t> From: <toby at gottfriedville.net>
njas> t> To: <njas at research.att.com>, <ed at mathpuzzle.com>
njas> t> Subject: Cannot find this particular result anywhere (A001045 - Jacobsthal numbers)
njas> t> Date: Sat, 1 Nov 2008 17:32:52 -0700
njas> t> 
njas> t> Someone on Yahoo Answers posed the question
njas> t> 
njas> t> "How many ways are there to tile a 2 x N rectangle
njas> t>     using 1x2 dominoes and 2x2 squares ?"
njas> t> 
njas> t> The result from a computer program was:
njas> t> 1,3,5,11,21,43,85,171,341,683,1365,2731,5461,10923,21845,43691
njas> > which is http://www.research.att.com/~njas/sequences/A001045
njas> t> the Jacobsthal numbers.
njas> t> 
njas> t> On that page it says 
njas> t>  Number of ways to tile a 3 X (n-1) rectangle with 1 X 1 and 2 X 2 square tiles.
njas> t> which is a similar problem.
njas> t> 
njas> t> Considering the basic nature of this problem
njas> t> and the number of other applications of this sequence,
njas> t> it would be quite a surprise if this were a new result,
njas> t> but after a fairly extensive search on Google, I could
njas> t> not find it anywhere.
njas> t> 
njas> t> Any comments ?

This seems to be obvious from the recurrence a(n)=a(n-1)+2a(n-2).
If you want to increase the 2XN rectangle by one unit to 2x(N+1),
you can either attach a 1x2 domino "vertically" to the 2xN case
or add two "horizontally stacked" or two "vertically stacked"  2x1
or one 2x2 domino to the 2X(N-1) case. So this naive argument would
yield a(n)=a(n-1)+3a(n-2), but it would have counted the case where
2xN ends with a vertically attached domino twice:

xxxxx  -> xxxx||   or -> xxxx--  or   xxxxSS
xxxxx     xxxx||         xxxx--       xxxxSS

where SS  is a 2x2 block.
      SS

where ||  is a 2 horizontally stacked 2x1 dominoes
      ||

where --  is a 2 vertically stacked 2x1 dominoes
      --

Richard