login
Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n such that the sum of the heights of their triangles is k (0<=k<=n). A triangle in a Dyck path is a subpath of the form U^h D^h, starting at the x-axis; here U=(1,1), D=(1,-1), h being the height of the triangle.
0

%I #4 Mar 06 2018 11:39:25

%S 1,0,1,0,0,2,1,0,0,4,4,1,0,0,8,12,4,2,0,0,16,33,12,8,4,0,0,32,88,33,

%T 24,16,8,0,0,64,232,88,66,48,32,16,0,0,128,609,232,176,132,96,64,32,0,

%U 0,256,1596,609,464,352,264,192,128,64,0,0,512,4180,1596,1218,928,704,528

%N Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n such that the sum of the heights of their triangles is k (0<=k<=n). A triangle in a Dyck path is a subpath of the form U^h D^h, starting at the x-axis; here U=(1,1), D=(1,-1), h being the height of the triangle.

%C Row sums are the odd-subscripted Fibonacci numbers (A001519). T(n,0)=fibonacci(2n-3)-1=A027941(n-2). Sum(k*T(n,k),k=0..n)=fibonacci(2n+1)-1=A027941(n).

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

%e T(5,2)=2 because we have (UD)(UD)UUDUDD and (UUDD)UUDUDD, where U=(1,1) and D=(1,-1) (the triangles are shown between parentheses).

%e Triangle starts:

%e 1;

%e 0,1;

%e 0,0,2;

%e 1,0,0,4;

%e 4,1,0,0,8;

%e 12,4,2,0,0,16;

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

%Y Cf. A001519, A027941.

%K nonn,tabl

%O 0,6

%A _Emeric Deutsch_, Aug 01 2006