%I
%S 1,7,13,20,35,66,118,218,402,738,1358,2498,4594,8450,15542,28586,
%T 52578,96706,177870,327154,601730,1106754,2035638,3744122,6886514,
%U 12666274,23296910,42849698,78812882,144959490,266622070
%N Number of basic blocks of size 5xn for tilings with square tiles of size up to 5 X 5.
%C Basic blocks of size 5xn are tilings of a 5xn area that cannot be vertically split into two smaller tilings of size 5xk and 5x(nk).
%H S. Heubach, <a href="https://www.calstatela.edu/sites/default/files/users/u1231/Papers/cgtc30.pdf">Tiling an mbyn area with squares of size up to kbyk (m<=5)</a>, Congressus Numerantium 140 (1999), 4364.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1).
%F a(n) = a(n1)+a(n2)+a(n3) for n>8, a(1)=1, a(2)=7, a(3)=13, a(4)=20, a(5)=35, a(6)=66, a(7)=218
%F G.f.: x^5+2*x^4x^3+5*x^2x10+2*(4*x+55*x^2)/(1xx^2x^3). a(n) = 10*A000213(n)8*A000073(n+1), n>5. [_R. J. Mathar_, Nov 02 2008]
%e a(3)=7 as the nature of basic blocks requires that the tiling cannot be split vertically into smaller tilings. Thus there needs to be one 2 X 2 tile whose lower left corner is in column 1 and one whose llc is in column 2. There are 7 ways to place these two 2 X 2 tiles.
%t f[ {A_, B_} ] := Module[ {til = A, basic = B}, {Flatten[ Append[ til, ListConvolve[ A, B ] ]], AppendTo[ basic, B[[ 1 ]] + B[[ 2 ]] + B[[ 3 ] ]]} ]; NumOfBasicBlocks[ n_ ] := Nest[ f, {{1, 1, 8, 28, 117, 472, 1916, 7765}, {1, 7, 13, 20, 35, 66, 118, 218}}, n2 ][[ 2 ]] NumOfBasicBlocks[ 30 ]
%t LinearRecurrence[{1,1,1},{1,7,13,20,35,66,118,218},40] (* _Harvey P. Dale_, Dec 06 2018 *)
%Y Cf. A054857.
%K easy,nonn
%O 1,2
%A Silvia Heubach (silvi(AT)cine.net), Apr 21 2000
