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,4

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

Links

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

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

Example

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;

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

Crossrefs

Cf. A001519, A121481, A121485, A121486.

Sequence in context: A330843 A115313 A048942 * A273903 A346420 A080928

Adjacent sequences: A121481 A121482 A121483 * A121485 A121486 A121487

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 02 2006

Status

approved