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,2

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

Links

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

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

Example

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.

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

Prog

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

Crossrefs

Cf. A109187, A002426.

Sequence in context: A258347 A323957 A026087 * A248437 A002532 A360023

Adjacent sequences: A109185 A109186 A109187 * A109189 A109190 A109191

Keyword

nonn

Author

Emeric Deutsch, Jun 21 2005

Status

approved