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,2

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).

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..52.

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.

Example

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

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

Crossrefs

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

Sequence in context: A184940 A185140 A111797 * A216121 A104546 A121632

Adjacent sequences: A122101 A122102 A122103 * A122105 A122106 A122107

Keyword

nonn,tabf

Author

Emeric Deutsch, Aug 24 2006

Extensions

Keyword tabf added by Michel Marcus, Apr 09 2013

Status

approved