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

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)=6 since we have 6 meanders of length 3, namely UHU, UDU, UHD, UDH, HUH and HUD.
		

Crossrefs

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

Programs

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

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).