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,5

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.

Links

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

Formula

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

Example

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.

Sequence in context: A104221 A078044 A348851 * A153993 A244781 A052907

Adjacent sequences: A329661 A329662 A329663 * A329665 A329666 A329667

Keyword

nonn,walk

Author

Valerie Roitner, Nov 19 2019

Status

approved