A329668 Number of meanders of length n with Motzkin-steps avoiding the consecutive steps HH and DU.

1, 2, 4, 9, 18, 38, 81, 171, 366, 787, 1693, 3661, 7938, 17240, 37540, 81892, 178907, 391483, 857769, 1881618, 4132225, 9083823, 19986954, 44014447, 97002134, 213933655, 472137851, 1042626752, 2303780392, 5093189194, 11265742842, 24930884645, 55196469010, 122255756284

Offset: 0

Author

Valerie Roitner, Nov 25 2019

Keywords

• nonn
• walk

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.

Examples

			a(3)=9 as one has 9 meanders of length 3, namely: UUU, UUH, UUD, UDH, UHU, UHD, HUU, HUD and HUH.
		

Crossrefs

Cf. A329666, which counts excursions with same restrictions.

Formula

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