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

Author

Emeric Deutsch, Aug 14 2006

Keywords

• nonn

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

Examples

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

Links

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

Crossrefs

Cf. A008275, A094638, A129177, A145888.

Programs

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

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

Extensions

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