|
%I #4 Mar 06 2018 11:39:01
%S 0,1,0,1,1,1,1,2,1,4,2,3,3,1,12,6,5,6,4,1,33,18,11,11,10,5,1,88,51,29,
%T 22,21,15,6,1,232,139,80,51,43,36,21,7,1,609,371,219,131,94,79,57,28,
%U 8,1,1596,980,590,350,225,173,136,85,36,9,1,4180,2576,1570,940,575,398
%N Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n, having k triangles (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)=A001906(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,k)=binomial(n,k)+Sum(binomial(n-j,k)*fibonacci(2j-4), j=1..n-k). G.f.=G=G(t,z)=(1-2z)^2/[(1-3z+z^2)(1-z-tz)].
%e T(4,1)=2 because we have (UD)UUDUDD and UUDUDD(UD), where U=(1,1) and D=(1,-1) (the triangles are shown between parentheses).
%e Triangle starts:
%e 1;
%e 0,1;
%e 0,1,1;
%e 1,1,2,1;
%e 4,2,3,3,1;
%e 12,6,5,6,4,1;
%p with(combinat): T:=(n,k)->binomial(n,k)+add(binomial(n-j,k)*fibonacci(2*j-4),j=1..n-k): for n from 0 to 12 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form
%Y Cf. A001519, A027941, A001906.
%K nonn,tabl
%O 0,8
%A _Emeric Deutsch_, Aug 01 2006
|
