A121637 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and having k 2-cell columns (n>=1; 0<=k<=n-1). 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, 1, 1, 2, 3, 1, 7, 10, 6, 1, 29, 47, 33, 10, 1, 147, 265, 210, 82, 15, 1, 889, 1740, 1521, 697, 171, 21, 1, 6252, 13087, 12373, 6377, 1885, 317, 28, 1, 50163, 111066, 112016, 63261, 21390, 4407, 540, 36, 1, 452356, 1050608, 1118991, 680541, 255245, 60903, 9247, 863, 45, 1

Offset

1,4

Comments

Row sums are the factorials (A000142). T(n,0)=A121638(n). Sum(k*T(n,k), k=0..n-1)=A121639(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=1..55.

Formula

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

Example

T(2,0)=1 and T(2,1)=1 because the deco polyominoes of height 2 are the horizontal and vertical dominoes, having, respectively, 0 and 1 2-cell columns.
Triangle starts:
   1;
   1,  1;
   2,  3,  1;
   7, 10,  6,  1;
  29, 47, 33, 10, 1;
  ...

Maple

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

Crossrefs

Cf. A000142, A121638, A121639, A121554.

Sequence in context: A256045 A173459 A354839 * A247370 A161847 A101175

Adjacent sequences: A121634 A121635 A121636 * A121638 A121639 A121640

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 13 2006

Status

approved