A134436 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n with k cells in the second row (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, 1, 3, 2, 1, 7, 10, 6, 1, 16, 37, 42, 24, 1, 44, 125, 214, 216, 120, 1, 169, 465, 959, 1406, 1320, 720, 1, 895, 2199, 4469, 7880, 10476, 9360, 5040, 1, 5942, 13504, 24902, 44203, 70676, 87732, 75600, 40320

Offset

1,5

Comments

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

Formula

The generating polynomial of row n is P(n,t)=Q(n,t,1), where Q(1,t,x)=x and Q(n,t,x)=xQ(n-1,1,t)+x(1+(n-2)t)Q(n-1,t,x) for n>=2.

Example

T(2,0)=T(2,1)=1 because the horizontal domino has no cells in the 2nd row and the vertical domino has 1 cell in the 2nd row.
Triangle starts:
1;
1,1;
1,3,2;
1,7,10,6;
1,16,37,42,24;

Maple

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

Crossrefs

Cf. A000142, A134437.

Sequence in context: A171128 A122832 A056151 * A306226 A186370 A163626

Adjacent sequences: A134433 A134434 A134435 * A134437 A134438 A134439

Keyword

nonn,tabl

Author

Emeric Deutsch, Nov 30 2007

Status

approved