%I #23 Aug 24 2020 22:42:35
%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