A121748 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and having k columns of even length (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, 1, 1, 2, 3, 1, 6, 11, 6, 1, 16, 44, 42, 16, 2, 66, 209, 254, 147, 40, 4, 246, 1005, 1647, 1377, 615, 138, 12, 1248, 5792, 11246, 11799, 7192, 2533, 474, 36, 5976, 33164, 78760, 104276, 83932, 41912, 12628, 2088, 144, 36120, 223676, 605854, 940399

Offset

1,4

Comments

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

References

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.

Links

Table of n, a(n) for n=1..49.

Formula

The row generating polynomials P[n](s) are given by P[n](s)=Q[n](1,s,1,s), where Q[n](t,s,x,y) are defined by Q[n](t,s,x,y)=Q[n-1](t,s,y,x)+[floor(n/2)*x+floor((n-1)/2)*y]Q[n-1](t,s,t,s) for n>=2 and Q[1](t,s,x,y]=x.

Example

T(2,0)=1 and T(2,1)=1 because the deco polyominoes of height 2 are the horizontal and vertical dominoes, having 0 and 1 columns of even length, respectively.
Triangle starts:
1;
1,1;
2,3,1;
6,11,6,1;
16,44,42,16,2;
66,209,254,147,40,4;

Maple

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

Crossrefs

Cf. A000142, A121745, A121749, A121750.

Sequence in context: A086960 A165675 A138771 * A174893 A008275 A130534

Adjacent sequences: A121745 A121746 A121747 * A121749 A121750 A121751

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 20 2006

Status

approved