A128098 Number of steps that touch the x-axis in all Motzkin paths of length n.

1, 4, 11, 30, 80, 214, 574, 1548, 4197, 11440, 31339, 86252, 238407, 661584, 1842585, 5148960, 14432643, 40569804, 114339777, 323031750, 914683602, 2595411126, 7378861196, 21016701652, 59962687675, 171353419536, 490407962229

Offset

1,2

Comments

a(n)=Sum(k*A128097(n,k), k=1..n).

Links

Table of n, a(n) for n=1..27.

Formula

G.f.=4[1-sqrt(1-2z-3z^2)]/[1-z+sqrt(1-2z-3z^2)]^2.

D-finite with recurrence (n-1)*(16*n-27)*(n+4)*a(n) -2*n*(16*n^2-3*n-28)*a(n-1) -3*n*(16*n-11)*(n-1)*a(n-2)=0. - R. J. Mathar, Jun 17 2016

Example

a(3)=11 because in the Motzkin paths of length 3 (namely HHH, HUD, UDH and UHD, where H=(1,0), U=(1,1) and D=(1,-1)) all the steps, with the exception of H in UHD, touch the x-axis.

Maple

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

Crossrefs

Cf. A128097.

Sequence in context: A110034 A340824 A114726 * A341104 A019495 A019496

Adjacent sequences: A128095 A128096 A128097 * A128099 A128100 A128101

Keyword

nonn

Author

Emeric Deutsch, Feb 16 2007

Status

approved