A054857 Number of ways to tile a 5 X n region with square tiles of size up to 5 X 5.

1, 1, 8, 28, 117, 472, 1916, 7765, 31497, 127707, 517881, 2100025, 8515772, 34532063, 140030059, 567832091, 2302600696, 9337214060, 37863085664, 153537580071, 622606110920, 2524713292359, 10237896957896, 41515420557135

Offset

0,3

Links

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

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.

Formula

a(n) = b(1)a(n-1)+b(2)a(n-2)+...+b(n)a(0), a(0)=a(1)=1, b(n) as defined in A054858.

a(n) = 2*a(n-1) +7*a(n-2) +6*a(n-3) -a(n-4) -5*a(n-5) -2*a(n-6) -3*a(n-7) -a(n-8). - R. J. Mathar, Nov 02 2008

G.f.: -(x^3+x^2+x-1)/(x^8+3*x^7+2*x^6+5*x^5+x^4-6*x^3-7*x^2-2*x+1). - Colin Barker, Jul 10 2012

Example

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

Mathematica

f[ {A_, B_} ] := Module[ {til = A, basic = B}, {Flatten[ Append[ til, ListConvolve[ A, B ] ] ], AppendTo[ basic, B[ [ -1 ] ] + B[ [ -2 ] ] + B[ [ -3 ] ] ]} ]; NumOfTilings[ n_ ] := Nest[ f, {{1, 1, 8, 28, 117, 472, 1916, 7765}, {1, 7, 13, 20, 35, 66, 118, 218}}, n - 2 ][ [ 1 ] ] NumOfTilings[ 30 ]

Crossrefs

Cf. A002478, A054856, A054858, A226548.

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

Sequence in context: A306545 A358285 A295914 * A241893 A200188 A255276

Adjacent sequences: A054854 A054855 A054856 * A054858 A054859 A054860

Keyword

nonn,easy

Author

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

Status

approved