A378810 - OEIS

A378810

Number of horizontal steps in all peak and valleyless Motzkin meanders of length n.

0, 1, 4, 13, 39, 110, 300, 801, 2106, 5473, 14097, 36056, 91697, 232108, 585212, 1470557, 3684682, 9209417, 22967446, 57167993, 142051519, 352427720, 873157093, 2160579740, 5340150100, 13185150903, 32523933395, 80156852042, 197391001215, 485723767342

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Motzkin meanders are lattice paths starting at (0,0) with steps Up (0,1), Horizontal (1,0), and Down (0,-1) that stay weakly above the x-axis. Peak and valleyless Motzkin meanders avoid UD and DU.

LINKS

Table of n, a(n) for n=0..29.

FORMULA

a(n) = Sum_{k=1..n} A378809(n,k)*k.

EXAMPLE

For n = 3 we have meanders, UUU, UUH, UHU, UHD, HUU, UHH, HHU, HUH, HHH; giving a total of a(3) = 13 H steps.

PROG

(PARI)

A088855(n, k) = {binomial(floor((n-1)/2), floor((k-1)/2))*binomial(ceil((n-1)/2), ceil((k-1)/2))}

A_xy(N) = {my(x='x+O('x^N), h = sum(n=0, N, (1/(1-y*x)^(n+1)) * (if(n<1, 1, 0) + sum(k=1, n, A088855(n, k)*x^(n+k-1)*(y^(k-1)) )) )); h}

P_xy(N) = Pol(A_xy(N), {x})

A_x(N) = {my(px = deriv(P_xy(N), y), y=1); Vecrev(eval(px))}