A121692 - OEIS

%I #30 Jul 22 2024 05:54:47

%S 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 1664,888,1,1,190,2412,8181,12458,11143,5934,1,1,382,7617,37739,81255,

%U 102558,87066,46261,1,1,766,23616,166573,489753,823597,941572,773772,409149,1

%N 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 Row sums are the factorials (A000142).

%C T(n,1) = 1,

%C T(n,2) = 3*2^(n-2) - 2 = A033484(n-2) for n >= 2.

%C T(n,3) = A121693(n).

%C Sum_{k=1..n} k*T(n,k) = A121694(n).

%H Alois P. Heinz, <a href="/A121692/b121692.txt">Rows n = 1..141, flattened</a>

%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 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 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 The second Maple program is based on these polynomials.

%e 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 Triangle starts:

%e   1;

%e   1,  1;

%e   1,  4,   1;

%e   1, 10,  12,   1;

%e   1, 22,  57,  39,   1;

%e   1, 46, 216, 293, 163, 1;

%e   ...

%p 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 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 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 Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 20 2024 *)

%Y Cf. A000142, A033484, A121693, A121694.

%Y T(2n,n) gives A374794.

%K nonn,tabl

%O 1,5

%A _Emeric Deutsch_, Aug 17 2006