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

Author

Emeric Deutsch, Jun 03 2008

Keywords

• nonn

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.

Examples

			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.
		

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.

Crossrefs

Cf. A000142, A011782, A140709.

Row sums of A227550/2.

Programs

Magma

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

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

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

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