A140709 - OEIS

%I #15 May 03 2021 01:25:01

%S 1,1,1,3,2,1,15,5,3,1,87,20,8,4,1,567,107,28,12,5,1,4167,674,135,40,

%T 17,6,1,34407,4841,809,175,57,23,7,1,316647,39248,5650,984,232,80,30,

%U 8,1,3219687,355895,44898,6634,1216,312,110,38,9,1,35878887,3575582,400793,51532,7850,1528,422,148,47,10,1

%N Triangle read by rows: T(n,k) is the number of deco polyominoes of height n in which the maximal number of initial consecutive columns ending at the same level is k (1 <= k <= n).

%C A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

%H G. C. Greubel, <a href="/A140709/b140709.txt">Rows n = 1..50 of the triangle, flattened</a>

%H E. Barcucci, A. Del Lungo and R. Pinzani, <a href="http://dx.doi.org/10.1016/0304-3975(95)00199-9">"Deco" polyominoes, permutations and random generation</a>, Theoretical Computer Science, 159, 1996, 29-42.

%F T(n,k) = binomial(n-1, k-1) + Sum_{j=2..n-1} j!*(j-1)*binomial(n-1-j, k-1).

%F T(n,k) = T(n-1, k) + T(n-1, k-1) for n,k >= 2.

%F Sum of entries in row n is n! (A000142).

%F T(n,1) = A132371(n).

%F Sum_{k=1..n} k*T(n,k) = A140710(n).

%e T(2,1)=1 (the vertical domino); T(2,2)=1 (the horizontal domino); T(3,1)=3 because we have (3), (1,2) and (2,1,1), where (a,b,c,...) stands for a polyomino with columns of lengths a,b,c,..., starting at level 0.

%e Triangle starts:

%e     1;

%e     1,   1;

%e     3,   2,   1;

%e    15,   5,   3,   1;

%e    87,  20,   8,   4,   1;

%e   567, 107,  28,  12,   5,   1;

%p T:=proc(n,k) options operator, arrow: binomial(n-1, k-1)+sum(factorial(j)*(j-1)*binomial(n-1-j, k-1),j=2..n-1) end proc: for n to 11 do seq(T(n, k),k=1..n) end do; # yields sequence in triangular form

%t T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[k==1, n! -Sum[j!, {j,n-1}], T[n-1, k] + T[n-1, k-1] ]];

%t Table[T[n, k], {n,14}, {k,n}]//Flatten (* _G. C. Greubel_, May 02 2021 *)

%o (PARI) T(n,k) = binomial(n-1, k-1) + sum(j=2, n-1, j!*(j-1)*binomial(n-1-j, k-1));

%o tabl(nn) = for (n=1, nn, for (k=1, n, print1(T(n,k), ", ")); print); \\ _Michel Marcus_, Nov 16 2019

%o (Sage)

%o @CachedFunction

%o def T(n, k):

%o     if (k < 0 or k > n): return 0

%o     elif (k==1): return factorial(n) - sum(factorial(j) for j in (1..n-1))

%o     else: return T(n-1, k-1) + T(n-1, k)

%o flatten([[T(n, k) for k in (1..n)] for n in (1..12)]) # _G. C. Greubel_, May 02 2021

%Y Cf. A000142, A132371, A140710.

%K nonn,tabl

%O 1,4

%A _Emeric Deutsch_, Jun 03 2008