OFFSET
1,5
COMMENTS
LINKS
Alois P. Heinz, Rows n = 1..141, flattened
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
Rec. relation: T(n,1) = 1; T(n,n) = 1; T(n,k) = k*T(n-1,k) + 2*T(n-1,k-1) + Sum_{j =1..k-2} T(n-1,j) for k <= n; T(n,k) = 0 for k > n.
Rec. relation for the row generating polynomials P[n](t): P[1] = t, P[n] = tP[n-1] + (t+t^2+...+t^(n-1))#P[n-1] for n >= 2. Here # stands for the "max-multiplication" of polynomials, a distributive operation, following the rule t^a # t^b = t^max(a,b).
The second Maple program is based on these polynomials.
EXAMPLE
T(2,1)=1 and T(2,2)=1 because the deco polyominoes of height 2 are the horizontal and vertical dominoes, having, respectively, 1 and 2 rows.
Triangle starts:
1;
1, 1;
1, 4, 1;
1, 10, 12, 1;
1, 22, 57, 39, 1;
1, 46, 216, 293, 163, 1;
...
MAPLE
T:=proc(n, k) option remember; if k=1 then 1 elif k=n then 1 elif k>n then 0 else k*T(n-1, k)+2*T(n-1, k-1)+add(T(n-1, j), j=1..k-2) fi: end: for n from 1 to 11 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form
with(linalg): a:=proc(i, j) if i=j then i elif i>j then 1 else 0 fi end: p:=proc(Q) local n, A, b, w, QQ: n:=degree(Q): A:=matrix(n, n, a): b:=j->coeff(Q, t, j): w:=matrix(n, 1, b): QQ:=multiply(A, w): sort(expand(add(QQ[k, 1]*t^k, k=1..n)+t*Q)): end: P[1]:=t: for n from 2 to 11 do P[n]:=p(P[n-1]) od: for n from 1 to 11 do seq(coeff(P[n], t, j), j=1..n) od; # yields sequence in triangular form
MATHEMATICA
T[n_, k_] := T[n, k] = Which[k == 1, 1, k == n, 1, k > n, 0, True, k*T[n - 1, k] + 2*T[n - 1, k - 1] + Sum[T[n - 1, j], {j, 1, k - 2}]];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 20 2024 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Aug 17 2006
STATUS
approved