A121582 Number of cells in column 2 of all deco polyominoes of height n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

0, 1, 7, 40, 252, 1837, 15259, 141798, 1455694, 16360387, 199845957, 2637020884, 37388864368, 566971338009, 9157693715407, 156975522127762, 2846305448882274, 54432896145210943, 1095019542858729769

Offset

1,3

Comments

a(n)=Sum(k*A121581(n,k),k=0..n-1).

References

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

Links

Harvey P. Dale, Table of n, a(n) for n = 1..400

Formula

a(1)=0, a(2)=1, a(n)=[(2n-3)a(n-1)-(n-1)a(n-2)+(n-1)!(n-2)(n^2-3n+4)/2]/(n-2) for n>=3.

a(n) ~ n*n!/2. - Vaclav Kotesovec, Aug 15 2013

D-finite with recurrence (-49*n+454)*a(n) +(49*n^2-454*n-1328)*a(n-1) +(49*n^2+1553*n-1464)*a(n-2) +(-581*n^2+612*n+1035)*a(n-3) +(819*n^2-3682*n+4007)*a(n-4) -4*(84*n-169)*(n-4)*a(n-5)=0. - R. J. Mathar, Jul 26 2022

Example

a(2)=1 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having, respectively, 0 and 1 cells in their second columns.

Maple

a:=proc(n) if n=1 then 0 elif n=2 then 1 else ((2*n-3)*a(n-1)-(n-1)*a(n-2)+(n-1)!*(n-2)*(n^2-3*n+4)/2)/(n-2) fi end: seq(a(n), n=1..22);

Mathematica

RecurrenceTable[{a[1]==0, a[2]==1, a[n]==((2n-3)a[n-1]-(n-1)a[n-2]+ (n-1)!(n-2) (n^2-3n+4)/2)/(n-2)}, a, {n, 20}] (* Harvey P. Dale, Oct 23 2012 *)

Crossrefs

Cf. A121580, A121581, A121584.

Sequence in context: A371813 A051814 A154968 * A239989 A356459 A226223

Adjacent sequences: A121579 A121580 A121581 * A121583 A121584 A121585

Keyword

nonn

Author

Emeric Deutsch, Aug 11 2006

Status

approved