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

Author

Emeric Deutsch, Jun 22 2005

Keywords

• nonn

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

Examples

			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).
		

Links

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

Crossrefs

Cf. A109194, A109195.

Programs

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 *)

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