cp's OEIS Frontend

A121692 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and vertical height (i.e., number of rows) k (1 <= 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.

%I A121692 #30 Jul 22 2024 05:54:47
%S A121692 1,1,1,1,4,1,1,10,12,1,1,22,57,39,1,1,46,216,293,163,1,1,94,741,1651,
%T A121692 1664,888,1,1,190,2412,8181,12458,11143,5934,1,1,382,7617,37739,81255,
%U A121692 102558,87066,46261,1,1,766,23616,166573,489753,823597,941572,773772,409149,1
%N A121692 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and vertical height (i.e., number of rows) k (1 <= 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 A121692 Row sums are the factorials (A000142).
%C A121692 T(n,1) = 1,
%C A121692 T(n,2) = 3*2^(n-2) - 2 = A033484(n-2) for n >= 2.
%C A121692 T(n,3) = A121693(n).
%C A121692 Sum_{k=1..n} k*T(n,k) = A121694(n).
%H A121692 Alois P. Heinz, <a href="/A121692/b121692.txt">Rows n = 1..141, flattened</a>
%H A121692 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 A121692 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 A121692 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.
%F A121692 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).
%F A121692 The second Maple program is based on these polynomials.
%e A121692 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.
%e A121692 Triangle starts:
%e A121692   1;
%e A121692   1,  1;
%e A121692   1,  4,   1;
%e A121692   1, 10,  12,   1;
%e A121692   1, 22,  57,  39,   1;
%e A121692   1, 46, 216, 293, 163, 1;
%e A121692   ...
%p A121692 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
%p A121692 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
%t A121692 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}]];
%t A121692 Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 20 2024 *)
%Y A121692 Cf. A000142, A033484, A121693, A121694.
%Y A121692 T(2n,n) gives A374794.
%K A121692 nonn,tabl
%O A121692 1,5
%A A121692 _Emeric Deutsch_, Aug 17 2006