login
Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and having k columns of even 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 #17 Aug 21 2024 06:07:51

%S 1,1,1,2,3,1,6,11,6,1,16,44,42,16,2,66,209,254,147,40,4,246,1005,1647,

%T 1377,615,138,12,1248,5792,11246,11799,7192,2533,474,36,5976,33164,

%U 78760,104276,83932,41912,12628,2088,144,36120,223676,605854,940399,919920,586721,243290,63028,9216,576

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

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

%H Elena Barcucci, Sara Brunetti, and Francesco Del Ristoro, <a href="http://www.numdam.org/item?id=ITA_2000__34_1_1_0">Succession rules and deco polyominoes</a>, Theoret. Informatics Appl., 34, 2000, 1-14.

%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](s) are given by P[n](s)=Q[n](1,s,1,s), 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[1](t,s,x,y]=x.

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

%e Triangle starts:

%e 1;

%e 1, 1;

%e 2, 3, 1;

%e 6, 11, 6, 1;

%e 16, 44, 42, 16, 2;

%e 66, 209, 254, 147, 40, 4;

%e ...

%p Q[1]:=x: for n from 2 to 11 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 1 to 11 do P[n]:=sort(subs({y=s,x=1,t=1},Q[n])) od: for n from 1 to 11 do seq(coeff(P[n],s,j),j=0..n-1) od; # yields sequence in triangular form

%t Q[n_] := Q[n] = If[n == 1, x, 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}]]];

%t P[n_] := P[n] = ReplaceAll[Q[n], {y -> s, x -> 1, t -> 1}];

%t T[n_, k_] := Coefficient[P[n], s, k];

%t Table[T[n, k], {n, 0, 10}, {k, 0, n-1}] // Flatten (* _Jean-François Alcover_, Aug 20 2024, after Maple Program *)

%Y Cf. A000142, A121745, A121749, A121750.

%K nonn,tabl

%O 1,4

%A _Emeric Deutsch_, Aug 20 2006