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

1, 1, 1, 2, 2, 1, 4, 6, 2, 1, 8, 13, 10, 2, 1, 16, 34, 23, 13, 2, 1, 33, 74, 75, 32, 16, 2, 1, 66, 178, 180, 124, 40, 19, 2, 1, 136, 390, 497, 321, 180, 48, 22, 2, 1, 274, 895, 1192, 1004, 488, 244, 56, 25, 2, 1, 562, 1958, 3033, 2598, 1701, 682, 317, 64, 28, 2, 1, 1138, 4374

Offset: 1

Author

Emeric Deutsch, Aug 02 2006

Keywords

• nonn
• tabl

Comments

Row sums are the odd-subscripted Fibonacci numbers (A001519). T(n,0)=A121485(n). Sum(k*T(n,k),k=0..n-1)=A121486(n).

Examples

			T(4,2)=2 because we have UDUU|DU|DD and UU|DDUU|DD, where U=(1,1) and D=(1,-1) (the peaks at even level are shown by a |).
Triangle starts:
1;
1,1;
2,2,1;
4,6,2,1;
8,13,10,2,1;
16,34,23,13,2,1;
		

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, A121481, A121485, A121486.

Programs

Maple

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

Formula

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