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

Author

Emeric Deutsch, Aug 05 2006

Keywords

• nonn
• tabf

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

Examples

			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;
		

Links

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

Crossrefs

Cf. A001519, A121529, A121532.

Programs

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

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