A329667 Number of meanders of length n with Motzkin-steps avoiding the consecutive steps UU and HH.

1, 2, 3, 6, 11, 21, 42, 83, 167, 341, 697, 1437, 2983, 6211, 12996, 27304, 57528, 121601, 257759, 547652, 1166299, 2489010, 5321780, 11398972, 24456235, 52549847, 113077188, 243645011, 525630690, 1135309380, 2454863253, 5313639848, 11512892983, 24967852309

Offset

0,2

Comments

The Motzkin step set is U=(1,1), H=(1,0) and D=(1,-1). A meander is a path starting at (0,0) and never crossing the x-axis, i.e. staying at nonnegative altitude.

Links

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

Formula

G.f.: (1/2)*(1-t^3-3*t^2-sqrt(t^6+2*t^5-3*t^4-6*t^3-2*t^2+1))*(t+1)/((t^2+2*t-1)*t^2).

Example

a(3)=6 since we have 6 meanders of length 3, namely UHU, UDU, UHD, UDH, HUH and HUD.

Prog

(PARI) my(t='t+O('t^40)); Vec((1/2)*(1-t^3-3*t^2-sqrt(t^6+2*t^5-3*t^4-6*t^3-2*t^2+1))*(t+1)/((t^2+2*t-1)*t^2)) \\ Michel Marcus, Nov 25 2019

Crossrefs

Cf. A329666 (excursions with same forbidden consecutive steps).

Sequence in context: A008930 A339151 A164362 * A026742 A316471 A018268

Adjacent sequences: A329664 A329665 A329666 * A329668 A329669 A329670

Keyword

nonn,walk

Author

Valerie Roitner, Nov 25 2019

Status

approved