A121483 Number of peaks at odd 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, 2, 6, 19, 56, 167, 487, 1411, 4047, 11527, 32617, 91790, 257065, 716896, 1991792, 5515535, 15227846, 41930133, 115176023, 315676425, 863475561, 2357539227, 6425887551, 17487572124, 47522431681, 128969086382, 349567320762

Offset

1,2

Comments

a(n) = Sum(k*A121481(n,k),k=0..n).

Links

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

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-z)(1-3z+6z^3-3z^4)/[(1+z)(1-3z+z^2)^2*(1-z-z^2)].

Recurrence: (n^2 - 5*n - 20)*a(n) = (3*n^2 - 12*n - 79)*a(n-1) + (n^2 - 7*n - 16)*a(n-2) - (5*n^2 - 19*n - 138)*a(n-3) - (n^2 - 6*n - 31)*a(n-4) + (n^2 - 3*n - 24)*a(n-5). - Vaclav Kotesovec, Mar 20 2014

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

Example

a(2)=2 because in UDUD and UUDD we have altogether 2 peaks at odd level; here U=(1,1) and D=(1,-1).

Maple

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

Mathematica

Rest[CoefficientList[Series[x*(1-x)*(1-3*x+6*x^3-3*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. A121481, A121486, A038731.

Sequence in context: A183305 A192715 A226433 * A077834 A325918 A307564

Adjacent sequences: A121480 A121481 A121482 * A121484 A121485 A121486

Keyword

nonn

Author

Emeric Deutsch, Aug 02 2006

Status

approved