A121693 Number of deco polyominoes of height n and vertical height 3 (i.e., having 3 rows).

0, 0, 1, 12, 57, 216, 741, 2412, 7617, 23616, 72381, 220212, 666777, 2012616, 6062421, 18236412, 54807537, 164619216, 494250861, 1483539012, 4452189897, 13359715416, 40085437701, 120268896012, 360831853857, 1082545893216

Offset: 1

Author

Emeric Deutsch, Aug 17 2006

Keywords

• nonn
• easy

Comments

A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

Links

• E. Barcucci, S. Brunetti and F. Del Ristoro, Succession rules and deco polyominoes, Theoret. Informatics Appl., 34, 2000, 1-14.
• E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
• Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

Crossrefs

Cf. A121692.

Programs

Maple

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

Formula

a(n) = A121692(n,3).

a(n) = 23*3^(n-3)/2 + 3/2 - 3*2^(n-1) for n >= 3.

Recurrence relation: a(n) = 3(a(n-1) + 2^(n-2) - 1) for n >= 4, a(1) = a(2) = 0, a(3) = 1.

G.f. = x^3*(1+6x-4x^2)/((1-x)(1-2x)(1-3x)).