A121638 Number of deco polyominoes of height n, having no 2-cell columns. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

1, 1, 2, 7, 29, 147, 889, 6252, 50163, 452356, 4529812, 49878095, 598989496, 7791393260, 109129383735, 1637539745521, 26208427321596, 445652393850867, 8023380629061127, 152470440379483009, 3049854459983511047, 64054967040282793114, 1409361745326600931517

Offset

1,3

Comments

a(n) = A121637(n,0).

References

E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

Links

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

Formula

D-finite with recurrence a(n)=(n-1)a(n-1)+a(n-3) for n>=3; a(1)=1, a(2)=1, a(3)=2.

Example

a(2)=1 because the deco polyominoes of height 2 are the horizontal and vertical dominoes and only the horizontal one has no 2-cell column.

Maple

a[1]:=1: a[2]:=1: a[3]:=2: for n from 4 to 23 do a[n]:=(n-1)*a[n-1]+a[n-3] od: seq(a[n], n=1..23);

Crossrefs

Cf. A121637, A001053.

Sequence in context: A030973 A295225 A030805 * A030874 A030920 A030824

Adjacent sequences: A121635 A121636 A121637 * A121639 A121640 A121641

Keyword

nonn

Author

Emeric Deutsch, Aug 14 2006

Status

approved