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

Author

Emeric Deutsch, Aug 14 2006

Keywords

• nonn

Comments

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

Examples

			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.
		

References

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

Crossrefs

Cf. A121637, A001053.

Programs

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);

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.