login
Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and having k columns of odd length (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

%I #13 Aug 19 2024 15:45:46

%S 1,0,1,1,0,1,1,3,1,1,3,6,9,4,2,9,28,36,30,13,4,27,107,195,198,130,51,

%T 12,117,532,1106,1371,1096,585,197,36,459,2573,6547,9914,9886,6733,

%U 3132,932,144,2421,15139,43606,76017,88793,72689,42200,17027,4412,576,11979,87362,293146,597856,824343,807930,574837,296296,107231,24940,2880

%N Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and having k columns of odd length (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.

%C Row sums are the factorials (A000142).

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

%C Sum_{k=0..n} k * T(n,k) = A121747(n).

%H Elena Barcucci, Alberto Del Lungo, and Renzo Pinzani, <a href="https://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 P[n](t) are given by P[n](t)=Q[n](t,1,t,1), where Q[n](t,s,x,y) are defined by Q[n](t,s,x,y)=Q[n-1](t,s,y,x)+[floor(n/2)*x+floor((n-1)/2)*y]Q[n-1](t,s,t,s) for n>=2 and Q[0](t,s,x,y)=1, Q[1](t,s,x,y]=x.

%e T(2,0)=1, T(2,1)=0 and T(2,2)=1 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having 0 and 2 columns of odd length, respectively.

%e Triangle starts:

%e 1;

%e 0, 1;

%e 1, 0, 1;

%e 1, 3, 1, 1;

%e 3, 6, 9, 4, 2;

%e 9, 28, 36, 30, 13, 4;

%e ...

%p Q[0]:=1: Q[1]:=x: for n from 2 to 10 do Q[n]:=expand(subs({x=y,y=x},Q[n-1])+(floor(n/2)*x+floor((n-1)/2)*y)*subs({x=t,y=s},Q[n-1])) od: for n from 0 to 10 do P[n]:=sort(subs({x=t,y=1,s=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

%t Q[0] = 1; Q[1] = x;

%t Do[Q[n] = Expand[ReplaceAll[Q[n-1], {x -> y, y -> x}] + (Floor[n/2]*x + Floor[(n-1)/2]*y)*ReplaceAll[Q[n-1], {x -> t, y -> s}]] , {n, 2, 10}];

%t Do[P[n] = ReplaceAll[Q[n], {x -> t, y -> 1, s -> 1}], {n, 0, 10}];

%t Table[Coefficient[P[n], t, j], {n, 0, 10}, {j, 0, n}] // Flatten (* _Jean-François Alcover_, Aug 19 2024, after Maple program *)

%Y Cf. A000142, A121746, A121747, A121748.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Aug 20 2006