login
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.
3
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.
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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Aug 08 2006
STATUS
approved