A121487 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, 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, 89, 34, 13, 5, 2, 1, 233, 610, 233, 89, 34, 13, 5, 2, 1, 610, 1597, 610, 233, 89, 34, 13, 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

Offset

1,4

Comments

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

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

Links

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.

Formula

T(n,k) = fibonacci(2n-2k-1) if k<n; T(n,n)=fibonacci(2n-3).

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)).

Example

T(4,2)=2 because we have UUDDUUDD and UUDDUDUD, where U=(1,1) and D=(1,-1).
Triangle starts:
1;
1,1;
2,1,2;
5,2,1,5;
13,5,2,1,13;
34,13,5,2,1,34;

Maple

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

Mathematica

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 *)

Prog

(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

Crossrefs

Cf. A001519.

Sequence in context: A337224 A090079 A165195 * A057031 A230219 A147292

Adjacent sequences: A121484 A121485 A121486 * A121488 A121489 A121490

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 03 2006

Status

approved