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

 

Logo


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

%I

%S 1,1,5,13,40,117,348,1029,3049,9028,26738,79183,234502,694476,2056692,

%T 6090891,18038173,53420041,158203433,468519406,1387520047,4109140098,

%U 12169216863,36039131181,106729873498,316080480394,936072224321

%N 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.

%C 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

%H S. Heubach, <a href="https://www.calstatela.edu/sites/default/files/users/u1231/Papers/cgtc30.pdf">Tiling an m-by-n area with squares of size up to k-by-k (m<=5)</a>, Congressus Numerantium 140 (1999), 43-64.

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,3,0,-1,-1).

%F 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

%F 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

%e 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.

%p 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

%t 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 ]

%Y Cf. A002478, A054857, A226547.

%Y Column k=4 of A219924. - _Alois P. Heinz_, Dec 01 2012

%K nonn,easy

%O 0,3

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

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 January 20 13:44 EST 2021. Contains 340302 sequences. (Running on oeis4.)