login
Triangle read by rows: T(n,k) is the number of deco polyominoes of height n having along the lower contour exactly k reentrant corners, i.e., a vertical step that is followed by a horizontal step (n>=1, k>=0).
2

%I #8 Jul 22 2017 08:35:26

%S 1,2,5,1,16,8,65,52,3,326,344,50,1957,2473,595,15,13700,19676,6524,

%T 420,109601,173472,71862,7840,105,986410,1686912,823836,127232,4410,

%U 9864101,17981193,9976686,1975750,118125,945,108505112,208769296,128350992

%N Triangle read by rows: T(n,k) is the number of deco polyominoes of height n having along the lower contour exactly k reentrant corners, i.e., a vertical step that is followed by a horizontal step (n>=1, k>=0).

%C A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

%C Row n contains ceiling(n/2) terms.

%C Row sums are the factorials (A000142).

%C T(n,0) = A000522(n).

%C T(2n+1,n) = (2n-1)!! = A001147(n) (the double factorials).

%C Sum_{k=0..n} k*T(n,k) = A002538(n-2) for n >= 3.

%H E. Barcucci, A. Del Lungo and R. Pinzani, <a href="http://dx.doi.org/10.1016/0304-3975(95)00199-9">"Deco" polyominoes, permutations and random generation</a>, Theoretical Computer Science, 159, 1996, 29-42.

%F The row generating polynomials are P(n,t) = Q(n,t,1), where Q(1,t,x) = 1 and Q(n,t,x) = Q(n-1,t,t) + (n-1)xQ(n-1,t,1) for n >= 2.

%e T(2,0)=2 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having no reentrant corners along the lower contour.

%e Triangle starts:

%e 1;

%e 2;

%e 5, 1;

%e 16, 8;

%e 65, 52, 3;

%e 326, 344, 50;

%p Q[1]:=1: for n from 2 to 13 do Q[n]:=sort(expand(subs(x=t,Q[n-1])+(n-1)*x*subs(x=1,Q[n-1]))) od: for n from 1 to 13 do P[n]:=subs(x=1,Q[n]) od: for n from 1 to 13 do seq(coeff(P[n],t,j),j=0..ceil(n/2)-1) od; # yields sequence in triangular form

%Y Cf. A000142, A000522, A001147, A002538.

%K nonn,tabf

%O 1,2

%A _Emeric Deutsch_, Aug 08 2006