A121298 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, 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, 0, 9, 75, 175, 223, 128, 0, 0, 0, 4, 78, 269, 479, 511, 256, 0, 0, 0, 1, 67, 358, 845, 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

Offset: 1

Author

Emeric Deutsch, Aug 04 2006

Keywords

• nonn
• tabl

Comments

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).

Examples

			T(2,2)=2 because we have the vertical and the horizontal dominoes.
Triangle starts:
1;
0,2;
0,1,4;
0,0,5,8;
0,0,3,15,16;
0,0,1,17,39,32;
		

Links

• E. Barcucci, A. Del Lungo, R. Pinzani and R. Sprugnoli, La hauteur des polyominos dirigés verticalement convexes, Actes du 31e Séminaire Lotharingien de Combinatoire, Publi. IRMA, Université Strasbourg I (1993).
• E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.

Crossrefs

Cf. A001519, A007808, A121299.

Programs

Maple

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

Mathematica

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}]];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 25 2024, after Maple program *)

Formula

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).