login
A140710
Number of maximal initial consecutive columns ending at the same level, summed over all deco polyominoes of height n.
3
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
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
Row sums of A227550/2.
Sequence in context: A306022 A186367 A010842 * A103296 A259859 A298940
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jun 03 2008
STATUS
approved