A121586 Number of columns in 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.

1, 1, 3, 13, 70, 446, 3276, 27252, 253296, 2602224, 29288160, 358457760, 4740577920, 67375532160, 1024208720640, 16583626886400, 284953145702400, 5178968115148800, 99268112350310400, 2001336861359001600, 42337994134947840000, 937755916997437440000

Offset

0,3

Comments

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. - Emeric Deutsch, Nov 10 2008

Links

Table of n, a(n) for n=0..21.

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

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(n-1) + (n-1)!*(n-1); (see the Barcucci et al. reference, p. 34).

a(n) = Sum_{k=1..n} k*A094638(n,k).

From Emeric Deutsch, Nov 10 2008: (Start)

a(n) = (n-1)!*(n^2 + n - 1 - n*H(n-1)) for n >= 1, where H(j) = 1/1+1/2+...+1/j.

a(n) = Sum_{k=1..n} k*A145888(n,k) for n >= 1. (End)

From Gary Detlefs, Sep 12 2010: (Start)

a(n) = n!*((n+1) - h(n)), where h(n) = Sum_{k=1..n} 1/k.

a(n) = (n+1)! - A000254(n). (End)

E.g.f.: (1 - (x - 1)*log(1 - x))/(x - 1)^2. - Benedict W. J. Irwin, Sep 27 2016

a(n) = Sum_{k=0..n*(n-1)/2} (k+1) * A129177(n,k). - Alois P. Heinz, May 04 2023

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[0] := 1; a[1] := 1: for n from 2 to 22 do a[n] := n*a[n-1] + (n-1)!*(n-1) od:
seq(a[n], n = 0..22);
# Second program:
egf := (1 - (x - 1)*log(1 - x))/(x - 1)^2: ser := series(egf, x, 20):
seq(n!*coeff(ser, x, n), n = 0..19); # Peter Luschny, Dec 09 2021

Mathematica

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

Crossrefs

Cf. A008275, A094638, A129177, A145888.

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

Extensions

a(0) = 1 prepended by Peter Luschny, Dec 09 2021

Status

approved