login
Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n and having abscissa of first return equal to 2k (1<=k<=n). A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing.
1

%I #8 Oct 23 2017 19:48:40

%S 1,1,1,2,1,2,5,2,1,5,13,5,2,1,13,34,13,5,2,1,34,89,34,13,5,2,1,89,233,

%T 89,34,13,5,2,1,233,610,233,89,34,13,5,2,1,610,1597,610,233,89,34,13,

%U 5,2,1,1597,4181,1597,610,233,89,34,13,5,2,1,4181,10946,4181,1597,610,233,89,34,13,5,2,1,10946

%N Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n and having abscissa of first return equal to 2k (1<=k<=n). A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing.

%C Row sums are the odd-subscripted Fibonacci numbers (A001519).

%C T(n,1) = T(n,n) = fibonacci(2n-3) = A001519(n-1) for n>=2.

%H G. C. Greubel, <a href="/A121487/b121487.txt">Table of n, a(n) for the first 50 rows, flattened</a>

%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) = fibonacci(2n-2k-1) if k<n; T(n,n)=fibonacci(2n-3).

%F G.f.: G(t,z) = t*z*(1-2*t*z)/(1-3*t*z+t^2*z^2)+t*z^2*(1-z)/((1-t*z)* (1-3*z+z^2)).

%e T(4,2)=2 because we have UUDDUUDD and UUDDUDUD, where U=(1,1) and D=(1,-1).

%e Triangle starts:

%e 1;

%e 1,1;

%e 2,1,2;

%e 5,2,1,5;

%e 13,5,2,1,13;

%e 34,13,5,2,1,34;

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

%t T[n_, k_] := If[k < n, Fibonacci[2*n - 2*k - 1], Fibonacci[2*n - 3]]; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _G. C. Greubel_, Oct 22 2017 *)

%o (PARI) for(n=1,10, for(k=1,n, print1(if(k<n, fibonacci(2*n-2*k-1), fibonacci(2*n-3)), ", "))) \\ _G. C. Greubel_, Oct 22 2017

%Y Cf. A001519.

%K nonn,tabl

%O 1,4

%A _Emeric Deutsch_, Aug 03 2006