

A121586


Number of columns in all deco polyominoes of height n. A deco polyomino is a directed columnconvex polyomino in which the height, measured along the diagonal, is attained only in the last column.


2



1, 3, 13, 70, 446, 3276, 27252, 253296, 2602224, 29288160, 358457760, 4740577920, 67375532160, 1024208720640, 16583626886400, 284953145702400, 5178968115148800, 99268112350310400, 2001336861359001600
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

From Emeric Deutsch, Nov 10 2008: (Start)
a(n) is also the largest entry in the cycle containing 1, summed over all permutations of {1,2,...,n}. Example: a(3)=13 because the permutations (1)(2)(3), (1)(23), (12)(3), (13)(2), (123), (132), written in cycle notation, yield 1+1+2+3+3+3=13.
a(n) = Sum(k*A145888(n,k), k=1..n). (End)


LINKS

Table of n, a(n) for n=1..19.
E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 2942.


FORMULA

a(n) = (n+1)!  s(n+1,2), where s(n,k) are the signed Stirling numbers of the first kind (A008275). Recurrence relation: a(n)=n*a(n1) + (n1)!*(n1); a(1)=1 (see the Barcucci et al. reference, p. 34).
a(n) = Sum(k*A094638(n,k), k=1..n).
a(n) = (n1)!*(n^2 + n  1  n*H(n1)), where H(j)=1/1+1/2+...+1/j. [Emeric Deutsch, Nov 10 2008]
From Gary Detlefs, Sep 12 2010: (Start)
a(n) = n!*((n+1)h(n)), where h(n)= sum(1/k,k=1..n)
a(n) = (n+1)! A000254(n) (End)
E.g.f.: ((x1)*log(1x)x1)/(x1)^3.  Benedict W. J. Irwin, Sep 27 2016


EXAMPLE

a(2)=3 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having, respectively, 1 and 2 columns.


MAPLE

a[1]:=1: for n from 2 to 22 do a[n]:=n*a[n1]+(n1)!*(n1) od: seq(a[n], n=1..22);


MATHEMATICA

Table[CoefficientList[Series[((x1)Log[1x]x1)/(x1)^3, {x, 0, 20}], x][[n]] (n1)!, {n, 1, 20}] (* Benedict W. J. Irwin, Sep 27 2016 *)


CROSSREFS

Cf. A008275, A094638.
Cf. A145888. [Emeric Deutsch, Nov 10 2008]
Sequence in context: A274379 A192209 A154677 * A024337 A001495 A284217
Adjacent sequences: A121583 A121584 A121585 * A121587 A121588 A121589


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Aug 14 2006


STATUS

approved



