A121694 Sum of the vertical heights (i.e., number of rows) of all deco polyominoes of height n.

1, 3, 12, 61, 377, 2734, 22671, 211035, 2175754, 24592551, 302295925, 4014475756, 57277225309, 873819665135, 14195291340656, 244657733062761, 4459137940238245, 85694418205589534, 1731893273528613811, 36721566227335477047, 815098440677104096866

Offset: 1

Author

Emeric Deutsch, Aug 17 2006

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(2)=3 because the deco polyominoes of height 2 are the horizontal and vertical dominoes, having, respectively, 1 and 2 rows.
		

Links

• E. Barcucci, S. Brunetti, and F. Del Ristoro, Succession rules and deco polyominoes, Theoret. Informatics Appl., 34, 2000, 1-14.
• E. Barcucci, A. Del Lungo, and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

Crossrefs

Cf. A121692.

Programs

Maple

with(linalg): a:=proc(i,j) if i=j then i elif i>j then 1 else 0 fi end: p:=proc(Q) local n,A,b,w,QQ: n:=degree(Q): A:=matrix(n,n,a): b:=j->coeff(Q,t,j): w:=matrix(n,1,b): QQ:=multiply(A,w): sort(expand(add(QQ[k,1]*t^k,k=1..n)+t*Q)): end: P[1]:=t: for n from 2 to 22 do P[n]:=p(P[n-1]) od: seq(subs(t=1,diff(P[n],t)),n=1..22);

Mathematica

(* T is A121692 *)
T[n_, k_] := T[n, k] = Which[k == 1, 1, k == n, 1, k > n, 0, True, k*T[n-1, k] + 2*T[n-1, k-1] + Sum[T[n-1, j], {j, 1, k-2}]];
a[n_] := Sum[k*T[n, k], {k, 1, n}];
Table[a[n], {n, 1, 21}] (* Jean-François Alcover, Aug 20 2024 *)

Formula

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

a(n) = Sum_{k=1..n} k*T(n,k), where T(n,k) (A121692) is defined by T(n,1)=1; T(n,n)=1; T(n,k) = k*T(n-1,k) + 2*T(n-1,k-1) + Sum_{j=1..k-2} T(n-1,j) for k <= n; T(n,k)=0 for k > n.