login
Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having k columns of height 1 starting at level 0.
0

%I #5 Mar 06 2018 11:41:07

%S 1,0,1,1,0,1,2,2,0,1,6,3,3,0,1,16,9,4,4,0,1,43,22,13,5,5,0,1,114,58,

%T 30,18,6,6,0,1,301,151,79,40,24,7,7,0,1,792,396,202,107,52,31,8,8,0,1,

%U 2080,1038,526,270,143,66,39,9,9,0,1,5456,2722,1370,701,358,188,82,48,10,10

%N Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having k columns of height 1 starting at level 0.

%C T(n,k) is the number of nondecreasing Dyck paths of semilength n, having k peaks at height 1. Example: T(4,2)=3 because we have UDUDUUDD, UDUUDDUD and UUDDUDUD, where U=(1,1) and D=(1,-1). sum(T(n,k),k=0..n)=fibonacci(2n-1) (A001519). sum(k*T(n,k),k=0..n)=fibonacci(2n-1) (A001519). T(n,0)=A027994(n-2) for n>=2.

%D E. Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.

%H E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)82778-1">Nondecreasing Dyck paths and q-Fibonacci numbers</a>, Discrete Math., 170, 1997, 211-217.

%F G.f.=(1-2z)^2/[(1-3z+z^2)(1-z-z^2-tz+tz^2)].

%e Triangle begins:

%e 1;

%e 0,1;

%e 1,0,1;

%e 2,2,0,1;

%e 6,3,3,0,1;

%p G:=(1-2*z)^2/(1-3*z+z^2)/(1-z-z^2-t*z+t*z^2):Gser:=simplify(series(G,z=0,14)): P[0]:=1: for n from 1 to 12 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 12 do seq(coeff(t*P[n],t^k),k=1..n+1) od;# yields sequence in triangular form

%Y Cf. A001519, A027994.

%K nonn,tabl

%O 0,7

%A _Emeric Deutsch_, Apr 26 2005