OFFSET
0,3
COMMENTS
Computed using a program with backtracking.
LINKS
Robert Gerbicz and Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n = 1..50 from Robert Gerbicz)
Terry Petrard, C program
Index entries for linear recurrences with constant coefficients, signature (2,0,1,-2,1,-1).
FORMULA
a(n) = a(n-1) + a(n-2) + a(n-3) + 2*r(n-3), where r(n) = r(n-1) + r(n-2) + a(n-2);
f(n) = f(n-1) + p(n) + q(n), where p(n) is the number of ways after filling 2 X n with a horizontal 2 X 1 domino and q(n) is the number of ways after filling 2 X n with a horizontal 3 X 1 domino.
r(n) is a 2 X n rectangle with 1 square removed from top left
p(n) is a 2 X n rectangle with 2 square removed from top left
q(n) is a 2 X n rectangle with 3 square removed from top left
p(n) = f(n-2) + r(n-2) (tiling with 2x1 gives f(n-2) and 3x1 gives r(n-2))
q(n) = f(n-3) + r(n-2) (tiling with 3x1 gives f(n-3) and 2x1 gives r(n-2))
r(n) = r(n-1) + p(n-2) (tiling with 2x1 gives r(n-1), tiling with a 3x1 gives p(n-2))
a(n)=2*a(n-1)+a(n-3)-2*a(n-4)+a(n-5)-a(n-6) - Robert Gerbicz, May 09 2008
G.f.: (1 - x - x^3)/((1-x)*(1-x-x^2-2*x^3-x^5)). - R. J. Mathar, Oct 30 2008
MATHEMATICA
LinearRecurrence[{2, 0, 1, -2, 1, -1}, {1, 2, 4, 7, 15, 30}, 40] (* Harvey P. Dale, Sep 02 2012 *)
PROG
(PARI) my(a=vector(50)); a[1]=1; a[2]=1; a[3]=2; a[4]=4; a[5]=7; a[6]=15; for(n=7, 50, a[n]=2*a[n-1]+a[n-3]-2*a[n-4]+a[n-5]-a[n-6]); a \\ Robert Gerbicz, May 09 2008
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Terry Petrard (temper3243(AT)gmail.com), May 04 2008
EXTENSIONS
More terms from Robert Gerbicz, May 09 2008
STATUS
approved