A109188 Number of (1,0) steps in all Grand Motzkin paths of length n.

1, 2, 9, 28, 95, 306, 987, 3144, 9963, 31390, 98483, 307836, 959257, 2981174, 9243405, 28601712, 88342659, 272428758, 838903371, 2579937060, 7924966749, 24317716038, 74546117121, 228317474952, 698708409525, 2136597743826

Offset: 1

Author

Emeric Deutsch, Jun 21 2005

Keywords

• nonn

Comments

A Grand Motzkin path 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).

Examples

			a(3)=9 because we have the following 7 (=A002426(3)) Grand Motzkin paths of length 3: hhh, hud, hdu, udh, duh, uhd and dhu; they have a total of 9 h-steps.
		

Links

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

Crossrefs

Cf. A109187, A002426.

Programs

Maple

g:=z*(1-z)/(1-2*z-3*z^2)^(3/2): gser:=series(g,z=0,33): seq(coeff(gser,z^n),n=1..30);
a := n -> n*hypergeom([1-n/2, 1/2-n/2], [1], 4):
seq(simplify(a(n)), n=1..26); # Peter Luschny, Sep 18 2014

Mathematica

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

PARI

Vec(z*(1-z)/(1-2*z-3*z^2)^(3/2) + O(z^50)) \\ G. C. Greubel, Jan 31 2017

Formula

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

a(n) = n*A002426(n-1). - Paul Barry, Apr 19 2008, corrected Nov 09 2021

E.g.f.: a(n) = n! * [x^n] exp(x)*((1 + x)*BesselI(0, 2*x) + 2*x*BesselI(1, 2*x)). - Peter Luschny, Aug 25 2012

D-finite with recurrence (-n+1)*a(n) + (3*n-4)*a(n-1) + (n+5)*a(n-2) + 3*(-n+2)*a(n-3) = 0. - R. J. Mathar, Nov 26 2012

a(n) = n*hypergeom([1-n/2, 1/2-n/2], [1], 4) . - Peter Luschny, Sep 18 2014

a(n) ~ 3^(n-1/2)*sqrt(n)/(2*sqrt(Pi)). - Vaclav Kotesovec, Sep 18 2014