A122104 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and such that the sum of the bottom levels of all columns is k (n>=1, k>=0; informally, the number of the "missing" cells in the right bottom corner of the polyomino). 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, 2, 5, 1, 16, 5, 3, 65, 23, 20, 10, 2, 326, 119, 115, 84, 57, 11, 8, 1957, 719, 714, 582, 526, 310, 137, 55, 34, 6, 13700, 5039, 5033, 4222, 4173, 3291, 2506, 972, 748, 348, 220, 38, 30, 109601, 40319, 40312, 34026, 34454, 29792, 28055, 18723, 10613, 6745

Offset: 1

Author

Emeric Deutsch, Aug 24 2006

Keywords

• nonn
• tabf

Comments

Row n has 1+floor((n-1)^2/4) terms. Row sums are the factorials (A000142). T(n,0)=A000522(n-1). T(n,1)=(n-1)!-1=A033312(n-1). T(n,2)=(n-1)!-n+1=A005096(n-1) for n>=2. Sum(k*T(n,k), k>=0)=A122105(n).

Examples

			Triangle starts:
1;
2;
5,1;
16,5,3;
65,23,20,10,2;
326,119,115,84,57,11,8;
		

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.

Crossrefs

Cf. A000142, A000522, A033312, A005096, A122105.

Programs

Maple

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

Formula

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

Extensions

Keyword tabf added by Michel Marcus, Apr 09 2013