A105262 a(n)=number of tilings of a 4 X n rectangle using tiles that are either 1 X 1 squares or trominoes (here by a tromino we mean a 2 X 2 square with the upper right 1 X 1 square removed; no rotations allowed).

1, 1, 5, 13, 42, 126, 387, 1180, 3606, 11012, 33636, 102733, 313781, 958384, 2927209, 8940617, 27307465, 83405605, 254747014, 778077690, 2376494563, 7258563604, 22169941574, 67713990832, 206819875428, 631693101321, 1929389878185

Offset

0,3

Links

Table of n, a(n) for n=0..26.

E. Deutsch, Counting tilings with L-tiles and squares, Problem 10877, Amer. Math. Monthly, 110 (March 2003), 245-246.

Index entries for linear recurrences with constant coefficients, signature (1,5,4,0,-1).

Formula

G.f.: ( 1-x^2-x^3 ) / ( (1+x)*(x^4-x^3-3*x^2-2*x+1) ).

a(n) = a(n-1)+5a(n-2)+4a(n-3)-a(n-5) for n>=5; a(0)=1, a(1)=1, a(2)=5, a(3)=13, a(4)=42.

Maple

a[0]:=1:a[1]:=1:a[2]:=5:a[3]:=13:a[4]:=42: for n from 5 to 30 do a[n]:=a[n-1]+5*a[n-2]+4*a[n-3]-a[n-5] od: seq(a[n], n=0..30);

Crossrefs

Sequence in context: A316536 A211383 A066873 * A298234 A129789 A093576

Adjacent sequences: A105259 A105260 A105261 * A105263 A105264 A105265

Keyword

nonn,easy

Author

Emeric Deutsch, Apr 15 2005

Status

approved