|
| |
|
|
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.
|
|
4
| |
|
|
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; 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+4z^2+2z^3+z^4+2z^3/(1-z); then G.f.=1/(1-g). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 16 2006
|
|
|
LINKS
| S. Heubach, Tiling an m X n area with squares of size up to k X k (m <=5), Congressus Numerantium 140 (1999), pp. 43-64.
|
|
|
FORMULA
| a(n)=a(n-1)+4a(n-2)+4a(n-3)+3a(n-4)+2( a(n-5)+a(n-6)+...+a(0)), a(0)=a(1)=1, a(2)=5, a(3)=13
a(n)=2a(n-1)+3a(n-2)-a(n-4)-a(n-5). G.f.=(1-z)/[(1+z)(1-3z+z^4)]. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), 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.
Sequence in context: A080143 A077919 A026069 * A121872 A025490 A087938
Adjacent sequences: A054853 A054854 A054855 * A054857 A054858 A054859
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Silvia Heubach (silvi(AT)cine.net), Apr 21 2000
|
| |
|
|
