A140710 Number of maximal initial consecutive columns ending at the same level, summed over all deco polyominoes of height n.

1, 3, 10, 38, 172, 944, 6208, 47696, 417952, 4101824, 44491648, 528068096, 6804155392, 94559581184, 1409615239168, 22434345998336, 379633330204672, 6805952938041344, 128854632579186688, 2568966172926181376

Offset

1,2

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

G. C. Greubel, Table of n, a(n) for n = 1..440

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

Formula

a(n) = 2^(n-1) * (1 + Sum_{j=1..n-1} j*j!/2^j ).

a(n) = (n-1)!*(n-1) + 2*a(n-1) with a(1) = 1.

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

(1 + x + 2*x^2 + 4*x^3 + 8*x^4 + ...)*(1 + 2*x + 6*x^2 + 24*x^3 + 120*x^4 + ...) = (1 + 3*x + 10*x^2 + 38*x^3 + 172*x^4 + ...) which is (Sum_{n>=0} A011782(n)*x^n) * (Sum_{n>=0} A000142(n+1)*x^n) = Sum_{n>=0} a(n+1)*x^n. - Gary W. Adamson, Feb 24 2012

a(n) = Sum_{j=0..n} (j+1)!*A011782(n-j) = (n+1)! + Sum_{j=0..n-1} 2^(n-k-1)*(j+1)!. - G. C. Greubel, May 03 2021

D-finite with recurrence a(n) +(-n-3)*a(n-1) +3*n*a(n-2) +2*(-n+2)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

Example

a(3)=10 because the 6 deco polyominoes of height 3 have columns ending at levels 3, 22, 12, 111, 22, 122, respectively and 1+2+1+3+2+1=10.

Maple

a:=proc(n) options operator, arrow: 2^(n-1)*(1+sum(j^2*factorial(j-1)/2^j, j= 1..n-1)) end proc: seq(a(n), n=1..20);

Mathematica

Table[2^(n-1)*(1 + Sum[j*j!/2^j, {j, n-1}]), {n, 30}] (* G. C. Greubel, May 02 2021 *)

Prog

(Magma) [2^(n-1)*(&+[j*Factorial(j)/2^j: j in [1..n-1]]): n in [1..30]]; // G. C. Greubel, May 02 2021
(Sage) [2^(n-1)*sum(j*factorial(j)/2^j for j in (1..n-1)) for n in (1..30)] # G. C. Greubel, May 02 2021

Crossrefs

Cf. A000142, A011782, A140709.

Row sums of A227550/2.

Sequence in context: A306022 A186367 A010842 * A103296 A259859 A298940

Adjacent sequences: A140707 A140708 A140709 * A140711 A140712 A140713

Keyword

nonn

Author

Emeric Deutsch, Jun 03 2008

Status

approved