login
Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n and height k (1<=k<=n; here by the height of a polyomino one means the number of lines of slope -1 that pass through the centers of the polyomino cells).
1

%I #9 Aug 25 2024 14:03:36

%S 1,0,2,0,1,4,0,0,5,8,0,0,3,15,16,0,0,1,17,39,32,0,0,0,15,59,95,64,0,0,

%T 0,9,75,175,223,128,0,0,0,4,78,269,479,511,256,0,0,0,1,67,358,845,

%U 1247,1151,512,0,0,0,0,48,419,1300,2461,3135,2559,1024,0,0,0,0,29,432,1801,4224,6813,7679,5631,2048

%N Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n and height k (1<=k<=n; here by the height of a polyomino one means the number of lines of slope -1 that pass through the centers of the polyomino cells).

%C Row sums are the odd-subscripted Fibonacci numbers (A001519). Sum of terms in column k = A007808(k). Sum(k*T(n,k),k=0..n)=A121299(n).

%H E. Barcucci, A. Del Lungo, R. Pinzani and R. Sprugnoli, <a href="http://www.mat.univie.ac.at/~slc/opapers/s31barc.html">La hauteur des polyominos dirigés verticalement convexes</a>, Actes du 31e Séminaire Lotharingien de Combinatoire, Publi. IRMA, Université Strasbourg I (1993).

%H E. Barcucci, R. Pinzani and R. Sprugnoli, <a href="http://dx.doi.org/10.1007/3-540-56610-4_71">Directed column-convex polyominoes by recurrence relations</a>, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.

%F T(n,k) = T(n-1,k-1)+Sum(T(n-k,j), j=1..k-1)+Sum(T(n-j,k-1), j=1..k-1).

%e T(2,2)=2 because we have the vertical and the horizontal dominoes.

%e Triangle starts:

%e 1;

%e 0,2;

%e 0,1,4;

%e 0,0,5,8;

%e 0,0,3,15,16;

%e 0,0,1,17,39,32;

%p T:=proc(n,k) if n<=0 or k<=0 then 0 elif n=1 and k=1 then 1 else T(n-1,k-1)+add(T(n-k,j),j=1..k-1)+add(T(n-j,k-1),j=1..k-1) fi end: for n from 1 to 12 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

%t T[n_, k_] := T[n, k] = Which[n <= 0 || k <= 0, 0, n == 1 && k == 1, 1, True, T[n-1, k-1] + Sum[T[n-k, j], {j, 1, k-1}] + Sum[T[n-j, k-1], {j, 1, k-1}]];

%t Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Aug 25 2024, after Maple program *)

%Y Cf. A001519, A007808, A121299.

%K nonn,tabl

%O 1,3

%A _Emeric Deutsch_, Aug 04 2006