A256943 Number of Grand Dyck-Motzkin paths of length n.

1, 1, 3, 6, 16, 38, 100, 254, 674, 1772, 4760, 12783, 34745, 94692, 260040, 716546, 1984984, 5517179, 15396331, 43094834, 121008580, 340686763, 961686971, 2720893669, 7715273753, 21921047638, 62401862460, 177948692666, 508289340032, 1454107965549

Offset

0,3

Comments

A Grand Dyck-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), such that H-steps are only allowed if y<=0.

Links

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

L. Ferrari and E. Munarini, Enumeration of edges in some lattices of paths , arXiv:1203.6792 [math.CO], 2012.

Formula

G.f.: 1/(1-x-x^2*C(x^2)-x^2*M(x)), where C(x) is the g.f. of Catalan numbers and M(x) is the g.f. of Motzkin paths.

a(n) ~ (3+sqrt(5)) * 3^(n+3/2) / (4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Apr 20 2015

Example

For instance, for n=3, we have the 6 paths UDH, HUD, HDU, DUH, DHU, HHH.

Mathematica

CoefficientList[Series[2/(Sqrt[1-4*x^2] + Sqrt[1-2*x-3*x^2] - x), {x, 0, 20}], x] (* Vaclav Kotesovec, Apr 20 2015 *)

Prog

(PARI) x='x+O('x^50); Vec(2/(sqrt(1-4*x^2) + sqrt(1-2*x-3*x^2) - x)) \\ G. C. Greubel, Mar 09 2017

Crossrefs

Cf. A002426.

Sequence in context: A114410 A190735 A096588 * A275207 A073079 A143560

Adjacent sequences: A256940 A256941 A256942 * A256944 A256945 A256946

Keyword

nonn

Author

José Luis Ramírez Ramírez, Apr 19 2015

Status

approved