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

Author

Emeric Deutsch, Jun 21 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) 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

Examples

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

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.

Crossrefs

Cf. A001006, A006355, A109189.

Programs

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

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

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