A109194 Number of returns to the x-axis (i.e., d or u steps hitting the x-axis) in all Grand Motzkin paths of length n. (A Grand Motzkin path of length n 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).).

2, 6, 22, 70, 224, 700, 2174, 6702, 20572, 62920, 191932, 584220, 1775258, 5386846, 16326734, 49435150, 149557436, 452133880, 1366012832, 4124825872, 12449394278, 37558361290, 113266431860, 341467468420, 1029119688014

Offset

2,1

Links

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

Formula

a(n) = Sum_{k=0..floor(n/2)} k*A109193(n,k).

a(n) = 2*A109196(n).

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

a(n) = 2*Sum_(k=1..n} ( Sum_{j=0..n} binomial(j,-n-2*k+2*j)*binomial(n,j)) ), n>1. - Vladimir Kruchinin, Oct 12 2011

a(n) ~ 3^n/2 * (1-sqrt(3/(Pi*n))). - Vaclav Kotesovec, Nov 05 2016

D-finite with recurrence n*a(n) +(-4*n+3)*a(n-1) +(-2*n+3)*a(n-2) +3*(4*n-9)*a(n-3) +9*(n-3)*a(n-4)=0. - R. J. Mathar, Jul 26 2022

Example

a(3)=6 because we have the following 7 (=A002426(3)) Grand Motzkin paths of length 3: hhh, hu(d), hd(u), u(d)h, d(u)h, uh(d) and dh(u); they have a total of 6 returns to the x-axis (shown between parentheses).

Maple

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

Mathematica

Drop[CoefficientList[Series[(1-x-Sqrt[1-2*x-3*x^2])/(1-2*x-3*x^2), {x, 0, 30}], x], 2] (* Vaclav Kotesovec, Nov 05 2016 *)

Prog

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

Crossrefs

Cf. A109193, A109196.

Sequence in context: A228396 A219766 A002839 * A014334 A107239 A262068

Adjacent sequences: A109191 A109192 A109193 * A109195 A109196 A109197

Keyword

nonn

Author

Emeric Deutsch, Jun 22 2005

Status

approved