login
A121748
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
1, 1, 1, 2, 3, 1, 6, 11, 6, 1, 16, 44, 42, 16, 2, 66, 209, 254, 147, 40, 4, 246, 1005, 1647, 1377, 615, 138, 12, 1248, 5792, 11246, 11799, 7192, 2533, 474, 36, 5976, 33164, 78760, 104276, 83932, 41912, 12628, 2088, 144, 36120, 223676, 605854, 940399, 919920, 586721, 243290, 63028, 9216, 576
OFFSET
1,4
COMMENTS
Row sums are the factorials (A000142).
T(n,0) = A121749(n).
Sum_{k=0..n} k * T(n,k) = A121750(n).
LINKS
Elena Barcucci, Sara Brunetti, and Francesco Del Ristoro, Succession rules and deco polyominoes, Theoret. Informatics Appl., 34, 2000, 1-14.
Elena Barcucci, Alberto Del Lungo, and Renzo Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
FORMULA
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.
EXAMPLE
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.
Triangle starts:
1;
1, 1;
2, 3, 1;
6, 11, 6, 1;
16, 44, 42, 16, 2;
66, 209, 254, 147, 40, 4;
...
MAPLE
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
MATHEMATICA
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}]]];
P[n_] := P[n] = ReplaceAll[Q[n], {y -> s, x -> 1, t -> 1}];
T[n_, k_] := Coefficient[P[n], s, k];
Table[T[n, k], {n, 0, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Aug 20 2024, after Maple Program *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Aug 20 2006
STATUS
approved