login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A129682 Number of ways tiling a 2 X n rectangle with 2 X 1 (domino) and 3 X 1 (tromino) tiles. 8
1, 1, 2, 4, 7, 15, 30, 60, 123, 249, 506, 1030, 2093, 4257, 8658, 17606, 35807, 72821, 148096, 301188, 612531, 1245717, 2533444, 5152318, 10478383, 21310119, 43338854, 88139182, 179250591, 364545863, 741384936, 1507770834, 3066386677, 6236177973, 12682652180 (list; graph; refs; listen; history; text; internal format)
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*(1-2*x^3+x^4-x^5)/((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) a=vector(50); a[1]=1; a[2]=2; a[3]=4; a[4]=7; a[5]=15; a[6]=30; 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

Column k=2 of A219866. - Alois P. Heinz, Nov 30 2012

Sequence in context: A232394 A115178 A049885 * A129981 A072964 A247291

Adjacent sequences:  A129679 A129680 A129681 * A129683 A129684 A129685

KEYWORD

nonn,easy

AUTHOR

Terry Petrard (temper3243(AT)gmail.com), May 04 2008

EXTENSIONS

More terms from Robert Gerbicz, May 09 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 26 19:29 EDT 2019. Contains 323597 sequences. (Running on oeis4.)