A109190 Number of (1,0)-steps at level zero in all Grand Motzkin paths of length n.

1, 0, 2, 2, 8, 16, 46, 114, 310, 822, 2238, 6094, 16764, 46308, 128650, 358862, 1005056, 2824416, 7962122, 22508350, 63792424, 181219680, 515905018, 1471593638, 4205280902, 12037415526, 34510499066, 99083855234, 284870069780

Offset

0,3

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) with steps u=(1,1), d=(1,-1) and h=(1,0).

Column 0 of A109189.

The substitution x->x/(1+x+x^2) in the g.f. (this might be called an inverse Motzkin transform), yields the g.f. of (-1)^n*A006355(n). - R. J. Mathar, Nov 10 2008

Apparently also the number of grand Motzkin paths of length n that avoid flat steps at level 0. - David Scambler, Jul 04 2013

Motzkin contexts such that along the path from the root to the hole there are only binary nodes. - Pierre Lescanne, Nov 11 2015

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Paul Barry, Moment sequences, transformations, and Spidernet graphs, arXiv:2307.00098 [math.CO], 2023.

Taras Goy and Mark Shattuck, Determinants of Some Hessenberg-Toeplitz Matrices with Motzkin Number Entries, J. Int. Seq., Vol. 26 (2023), Article 23.3.4.

Formula

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

G.f.: 1/(1-2x^2*M(x)), M(x) the g.f. of the Motzkin numbers A001006. - Paul Barry, Mar 02 2010

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

a(n) ~ 3^(n+3/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 03 2014

Example

a(3) = 2 because we have uhd and dhu.

Maple

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

Mathematica

CoefficientList[Series[(Sqrt[1-2*x-3*x^2]-x)/(1-2*x-4*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 03 2014 *)

Prog

(PARI) x='x+O('x^55); Vec((sqrt(1-2*x-3*x^2)-x)/(1-2*x-4*x^2)) \\ Altug Alkan, Nov 11 2015

Crossrefs

Cf. A001006, A006355, A109189.

Sequence in context: A228797 A052970 A220589 * A016120 A367071 A188115

Adjacent sequences: A109187 A109188 A109189 * A109191 A109192 A109193

Keyword

nonn

Author

Emeric Deutsch, Jun 21 2005

Status

approved