A121531 Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n and having k double rises at an even level (n >= 1, k >= 0). A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing.

1, 2, 4, 1, 7, 6, 12, 20, 2, 20, 51, 18, 33, 115, 80, 5, 54, 240, 262, 54, 88, 477, 725, 294, 13, 143, 916, 1803, 1158, 161, 232, 1716, 4170, 3768, 1026, 34, 376, 3155, 9152, 10815, 4684, 475, 609, 5717, 19311, 28418, 17432, 3449, 89, 986, 10240, 39520

Offset

1,2

Comments

Row n contains ceiling(n/2) terms.

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

T(n,0) = Fibonacci(n+2) - 1 = A000071(n+2).

Sum_{k>=0} k*T(n,k) = A121532(n).

Links

Table of n, a(n) for n=1..52.

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

Formula

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

Example

T(5,2)=2 because we have UU/UU/UDDDDD and UU/UDDU/UDDD, where U=(1,1) and D=(1,-1) (the double rises at an even level are indicated by a /).
Triangle starts:
   1;
   2;
   4,   1;
   7,   6;
  12,  20,  2;
  20,  51, 18;
  33, 115, 80, 5;

Maple

G:=z*(1-2*t*z^2-t*z^3)*(1-t*z^2)/(1-z-t*z^2)/(1-z-z^2-3*t*z^2-t*z^3+t^2*z^4): Gser:=simplify(series(G, z=0, 18)): for n from 1 to 15 do P[n]:=sort(coeff(Gser, z, n)) od: for n from 1 to 15 do seq(coeff(P[n], t, j), j=0..ceil(n/2)-1) od; # yields sequence in triangular form

Crossrefs

Cf. A001519, A121529, A121532.

Sequence in context: A207616 A105552 A112852 * A367065 A360180 A127554

Adjacent sequences: A121528 A121529 A121530 * A121532 A121533 A121534

Keyword

nonn,tabf

Author

Emeric Deutsch, Aug 05 2006

Status

approved