A329664 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UD, HH and DU.

1, 1, 0, 1, 2, 2, 4, 8, 12, 21, 40, 69, 122, 227, 412, 747, 1386, 2567, 4744, 8851, 16566, 31004, 58268, 109858, 207368, 392331, 744072, 1413291, 2688822, 5124738, 9781492, 18694896, 35780444, 68566567, 131546440, 252661515, 485806614, 935017790, 1801327884, 3473467328, 6703610548

Offset: 0

Author

Valerie Roitner, Nov 19 2019

Keywords

• nonn
• walk

Comments

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

Examples

			a(4)=2 as one has 2 excursions of length 4, namely: HUHD and UHDH.
		

Crossrefs

Cf. A004149 (avoiding UD and DU).

Cf. A329666, A329665.

Formula

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