A121523 Number of up steps starting at an even level in all nondecreasing Dyck paths of semilength n. A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing.

1, 3, 10, 33, 103, 315, 941, 2770, 8051, 23171, 66138, 187486, 528365, 1481501, 4135756, 11500721, 31871625, 88054825, 242609585, 666783380, 1828452021, 5003697403, 13667302500, 37267071708, 101455834153, 275797332135

Offset

1,2

Comments

a(n) = Sum(k*A121522(n,k), k=1..n). a(n)+A121525(n)=n*fibonacci(2n-1).

Links

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

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 (6,-9,-5,15,-1,-4,1).

Formula

G.f.: z(1-3z+z^2+5z^3-5z^4)/[(1+z)(1-3z+z^2)^2*(1-z-z^2)].

a(n) ~ (5-sqrt(5)) * (3+sqrt(5))^n * n / (5 * 2^(n+2)). - Vaclav Kotesovec, Mar 20 2014

Example

a(3)=10 because we have (U)D(U)D(U)D, (U)D(U)UDD, (U)UDD(U)D, (U)UDUDD and (U)U(U)DDD, the up steps starting at even level being shown between parentheses (U=(1,1), D=(1,-1)).

Maple

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

Mathematica

Rest[CoefficientList[Series[x*(1-3*x+x^2+5*x^3-5*x^4)/(1+x)/(1-3*x+x^2)^2 /(1-x-x^2), {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 20 2014 *)

Crossrefs

Cf. A001519, A121522, A121525.

Sequence in context: A316411 A292549 A062454 * A115240 A027989 A096483

Adjacent sequences: A121520 A121521 A121522 * A121524 A121525 A121526

Keyword

nonn

Author

Emeric Deutsch, Aug 05 2006

Status

approved