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
Examples
a(4)=4 because we have UDUDUDUD, UDUUUDDD, UUUDDDUD and UUUDUDDD, where U=(1,1) and D=(1,-1).
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).
Programs
-
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
-
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 *) -
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
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
Comments