A121554 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and having k 1-cell columns (0<=k<=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, 0, 1, 1, 0, 1, 2, 2, 1, 1, 7, 7, 6, 3, 1, 30, 35, 30, 18, 6, 1, 157, 205, 184, 117, 46, 10, 1, 972, 1392, 1304, 874, 381, 101, 15, 1, 6961, 10764, 10499, 7355, 3470, 1052, 197, 21, 1, 56660, 93493, 94668, 68909, 34622, 11606, 2542, 351, 28, 1, 516901, 901900

Offset

0,7

Comments

Row sums are the factorials (A000142). T(n,0)=A001053(n). Sum(k*T(n,k), k=0..n)=A121555(n).

References

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

Links

Table of n, a(n) for n=0..56.

Formula

The row generating polynomials are P(n,t)=Q(n,t,1), where Q(0,t,x)=1 and Q(n,t,x)=Q(n-1,t,1/t)+(tx+n-2)Q(n-1,t,1) for n>=1.

Example

T(2,0)=1, T(2,1)=0, T(2,2)=1 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having, respectively, 0 and 2 columns with exactly 1 cell.
Triangle starts:
1;
0,1;
1,0,1;
2,2,1,1;
7,7,6,3,1;
30,35,30,18,6,1;

Maple

Q[0]:=1: for n from 1 to 10 do Q[n]:=sort(expand(subs(x=1/t, Q[n-1])+(t*x+n-2)*subs(x=1, Q[n-1]))) od: for n from 0 to 10 do P[n]:=subs(x=1, Q[n]) od: for n from 0 to 10 do seq(coeff(P[n], t, j), j=0..n) od; # yields sequence in triangular form

Crossrefs

Cf. A000142, A001053, A121555.

Sequence in context: A340591 A155794 A107876 * A365077 A260360 A011296

Adjacent sequences: A121551 A121552 A121553 * A121555 A121556 A121557

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 08 2006

Status

approved