A121486 Number of peaks at 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.

0, 1, 4, 13, 43, 132, 400, 1184, 3461, 9999, 28634, 81383, 229860, 645731, 1805582, 5028189, 13952221, 38590922, 106434540, 292792026, 803565215, 2200694791, 6015268164, 16412564173, 44708036568, 121600924117, 330277253560

Offset

1,3

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.

E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.

Index entries for linear recurrences with constant coefficients, signature (6,-9,-5,15,-1,-4,1).

Formula

a(n) = Sum(k*A121484(n,k),k=0..n-1).

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

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

20*a(n) = -8*(-1)^n +10*(2*A001871(n)-5*A001871(n-1))+5*(4*A000045(n+1)-7*A000045(n))-3*(4*A001906(n+1)+9*A001906(n)). - R. J. Mathar, Jul 26 2022

Example

a(3)=4 because in UDUDUD, UDUU|DD, UU|DDUD, UU|DU|DD and UUUDDD we have altogether 4 peaks at even level (shown by a |); here U=(1,1) and D=(1,-1).

Maple

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

Mathematica

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

Crossrefs

Cf. A121484, A121483, A038731.

Sequence in context: A072307 A355116 A266494 * A339063 A188176 A003688

Adjacent sequences: A121483 A121484 A121485 * A121487 A121488 A121489

Keyword

nonn

Author

Emeric Deutsch, Aug 02 2006

Status

approved