A109196 Number of returns to the x-axis from above (i.e., d steps hitting the x-axis) in all Grand Motzkin paths of length n.

1, 3, 11, 35, 112, 350, 1087, 3351, 10286, 31460, 95966, 292110, 887629, 2693423, 8163367, 24717575, 74778718, 226066940, 683006416, 2062412936, 6224697139, 18779180645, 56633215930, 170733734210, 514559844007, 1550364293145

Offset

2,2

Comments

A Grand Motzkin path of length n is a path in the half-plane x >= 0, starting at (0,0), ending at (n,0) and consisting of steps u=(1,1), d=(1,-1) and h=(1,0).

The substitution x->x/(1+x+x^2), the inverse Motzkin transform, yields a g.f. for the sequence 0,0,2,2,6,4,..., that is 0 followed by 2*A026741(n-1). - R. J. Mathar, Nov 10 2008

Links

G. C. Greubel, Table of n, a(n) for n = 2..1000

Formula

G.f.: (1-z-sqrt(1-2*z-3*z^2)) / (2*(1-2*z-3*z^2)).

a(n) = Sum_{k=0..floor(n/2)} k*A109195(n,k).

a(n) = (1/2) * A109194(n).

From Benedict W. J. Irwin, Nov 02 2016: (Start)

Conjecture: a(n) = (2*(-1)^n + 2*3^n + (2^n*(2*n - 1)!!*(3*A - 4*B))/n! - 3*(n + 1)*C)/8.

A = 2F1(1-n,-n; 1/2-n; 1/4).

B = 2F1(-n,-n; 1/2-n; 1/4).

2^n*(2*n - 1)!!*(3*A - 4*B))/n! = A103872(n-2).

C = 3F2(1-n,(1-n)/2,-n/2; 2,-n-1; 4) = A025565(n)/n. (End)

a(n) ~ 3^n/4 * (1-sqrt(3/(Pi*n))). - Vaclav Kotesovec, Nov 05 2016

D-finite with recurrence n*a(n) +(-4*n+3)*a(n-1) +(-2*n+3)*a(n-2) +3*(4*n-9)*a(n-3) +9*(n-3)*a(n-4)=0. - R. J. Mathar, Feb 08 2021

Example

a(3)=3 because we have the following 7 (=A002426(3)) Grand Motzkin paths of length 3: hhh, hu(d), hdu, u(d)h, duh, uh(d) and dhu; they have a total of 3 returns from above to the x-axis (shown between parentheses).

Maple

g:=(1-z-sqrt(1-2*z-3*z^2))/2/(1-2*z-3*z^2): gser:=series(g, z=0, 32): seq(coeff(gser, z^n), n=2..30);

Mathematica

Rest[Rest[CoefficientList[Series[(1 - x - Sqrt[1 - 2 x - 3 x^2]) / (2 (1 - 2 x - 3 x^2)), {x, 0, 35}], x]]] (* Vincenzo Librandi, Nov 04 2016 *)

Crossrefs

Cf. A109194, A109195.

Sequence in context: A025181 A004054 A068995 * A032637 A034576 A125672

Adjacent sequences: A109193 A109194 A109195 * A109197 A109198 A109199

Keyword

nonn

Author

Emeric Deutsch, Jun 22 2005

Status

approved