|
Search: id:A054856
|
|
|
| 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. |
|
+0
3
|
|
| 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; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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.
Adjacent sequences: A054853 A054854 A054855 this_sequence A054857 A054858 A054859
Sequence in context: A080143 A077919 A026069 this_sequence A121872 A025490 A087938
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Silvia Heubach (silvi(AT)cine.net), Apr 21 2000
|
|
|
Search completed in 0.002 seconds
|
