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

%I #7 Mar 06 2018 11:38:09

%S 1,1,1,2,2,1,5,4,3,1,13,10,6,4,1,34,26,15,8,5,1,89,68,39,20,10,6,1,

%T 233,178,102,52,25,12,7,1,610,466,267,136,65,30,14,8,1,1597,1220,699,

%U 356,170,78,35,16,9,1,4181,3194,1830,932,445,204,91,40,18,10,1,10946,8362

%N Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having leftmost column of height k.

%C T(n,k) is the number of nondecreasing Dyck paths of semilength n, having height of leftmost peak equal to k. Example: T(3,2)=2 because we have UUDDUD and UUDUDD, where U=(1,1) and D(1,-1). Sum of row n = fibonacci(2n-1) (A001519). T(n,1)=fibonacci(2n-3) (A001519). Column 2 yields A055819.

%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 T(n, k)=k*fibonacci(2n-2k-1) if k<n; T(n, n)=1. G.f.=tz(1-2z-tz+3tz^2-tz^3)/[(1-3z+z^2)(1-tz)^2].

%e Triangle begins:

%e 1;

%e 1,1;

%e 2,2,1;

%e 5,4,3,1;

%e 13,10,6,4,1;

%p with(combinat):T:=proc(n,k) if k<n then k*fibonacci(2*n-2*k-1) elif k=n then 1 else 0 fi end:for n from 1 to 12 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

%t Flatten[Join[{1},#]&/@Table[k*Fibonacci[2n-2k-1],{n,15},{k,n-1}]] (* _Harvey P. Dale_, Aug 21 2013 *)

%Y Cf. A001519, A055819.

%K nonn,tabl

%O 1,4

%A _Emeric Deutsch_, Apr 25 2005