A121485 Number of nondecreasing Dyck paths of semilength n and having no peaks at even level (n>=0). A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing.

1, 1, 2, 4, 8, 16, 33, 66, 136, 274, 562, 1138, 2327, 4725, 9645, 19613, 39997, 81397, 165906, 337773, 688260, 1401565, 2855432, 5815477, 11846941, 24129498, 49152840, 100116607, 203936639, 415394872, 846143795, 1723513075, 3510704795

Offset

1,3

Comments

Column 0 of A121484.

Links

Colin Barker, Table of n, a(n) for n = 1..1000

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

Index entries for linear recurrences with constant coefficients, signature (1,4,-2,-4,0,1).

Formula

G.f.: z(1-z^2)(1-2z^2)/(1-z-4z^2+2z^3+4z^4-z^6).

a(n) = a(n-1)+4*a(n-2)-2*a(n-3)-4*a(n-4)+a(n-6) for n>6. - Colin Barker, Sep 11 2015

Example

a(4)=4 because we have UDUDUDUD, UDUUUDDD, UUUDDDUD and UUUDUDDD, where U=(1,1) and D=(1,-1).

Maple

G:=z*(1-z^2)*(1-2*z^2)/(1-4*z^2-z+4*z^4-z^6+2*z^3): Gser:=series(G, z=0, 40): seq(coeff(Gser, z, n), n=1..37);

Mathematica

LinearRecurrence[{1, 4, -2, -4, 0, 1}, {1, 1, 2, 4, 8, 16}, 40] (* Vincenzo Librandi, Sep 12 2015 *)

Prog

(PARI) Vec(z*(1-z^2)*(1-2*z^2)/(1-z-4*z^2+2*z^3+4*z^4-z^6) + O(z^60)) \\ Michel Marcus, Sep 11 2015
(Magma) I:=[1, 1, 2, 4, 8, 16]; [n le 6 select I[n] else Self(n-1)+4*Self(n-2)-2*Self(n-3)-4*Self(n-4)+Self(n-6): n in [1..40]]; // Vincenzo Librandi, Sep 12 2015

Crossrefs

Cf. A121482, A121484.

Sequence in context: A355548 A036373 A119610 * A308808 A324406 A182442

Adjacent sequences: A121482 A121483 A121484 * A121486 A121487 A121488

Keyword

nonn,easy

Author

Emeric Deutsch, Aug 02 2006

Status

approved