login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054856 Number of ways to tile a 4 X n region with 1 X 1, 2 X 2, 3 X 3 and 4 X 4 tiles. 7
1, 1, 5, 13, 40, 117, 348, 1029, 3049, 9028, 26738, 79183, 234502, 694476, 2056692, 6090891, 18038173, 53420041, 158203433, 468519406, 1387520047, 4109140098, 12169216863, 36039131181, 106729873498, 316080480394, 936072224321 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

It is easy to see that the g.f. for indecomposable tilings, i.e. those that cannot be split vertically into smaller tilings, is g=z+4*z^2+2*z^3+z^4+2*z^3/(1-z); then G.f.=1/(1-g). - Emeric Deutsch, Oct 16 2006

LINKS

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

S. Heubach, Tiling an m-by-n area with squares of size up to k-by-k (m<=5), Congressus Numerantium 140 (1999), 43-64.

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

FORMULA

a(n) = a(n-1)+4*a(n-2)+4*a(n-3)+3*a(n-4)+2*( a(n-5)+a(n-6)+...+a(0)), a(0)=a(1)=1, a(2)=5, a(3)=13

a(n) = 2*a(n-1)+3*a(n-2)-a(n-4)-a(n-5). G.f.=(1-z)/((1+z)*(1-3*z+z^4)). - Emeric Deutsch, Oct 16 2006

EXAMPLE

a(2)=5 as there is one tiling of a 4 X 2 region with only 1 X 1 tiles, 3 tilings with exactly one 2 X 2 tile and 1 tiling with exactly two 2 X 2 tiles.

MAPLE

a[0]:=1: a[1]:=1: a[2]:=5: a[3]:=13: a[4]:=40: for n from 5 to 26 do a[n]:=2*a[n-1]+3*a[n-2]-a[n-4]-a[n-5] od: seq(a[n], n=0..26); # Emeric Deutsch, Oct 16 2006

MATHEMATICA

f[ A_ ] := Module[ {til = A, sum}, sum = 2* Apply[ Plus, Drop[ til, -4 ] ]; AppendTo[ til, A[ [ -1 ] ] + 4A[ [ -2 ] ] + 4A[ [ -3 ] ] + 3A[ [ -4 ] ] + sum ] ]; NumOfTilings[ n_ ] := Nest[ f, {1, 1, 5, 13}, n - 2 ]; NumOfTilings[ 30 ]

CROSSREFS

Cf. A002478, A054857, A226547.

Column k=4 of A219924. - Alois P. Heinz, Dec 01 2012

Sequence in context: A272225 A272585 A026069 * A261057 A283456 A337339

Adjacent sequences:  A054853 A054854 A054855 * A054857 A054858 A054859

KEYWORD

nonn,easy

AUTHOR

Silvia Heubach (silvi(AT)cine.net), Apr 21 2000

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 November 26 15:56 EST 2020. Contains 338640 sequences. (Running on oeis4.)