A329692 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UU, HH, HD and DH.

1, 1, 1, 1, 1, 2, 2, 4, 5, 8, 13, 18, 32, 46, 77, 123, 192, 325, 506, 849, 1375, 2245, 3750, 6085, 10206, 16798, 27936, 46689, 77389, 130048, 216717, 363701, 610657, 1023965, 1726537, 2902221, 4898323, 8265964, 13957522, 23622321, 39949012, 67710936, 114768860, 194709672, 330693182

Offset

0,6

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 at (n,0) and never crossing the x-axis, i.e., staying at nonnegative altitude.

Links

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

Formula

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

Example

a(7)=4 since we have the following 4 excursions of length 7: UHUDDUD, UHUDUDD, UDUHUDD and HUDUDUD.

Mathematica

CoefficientList[Series[(1 + x)*(1 - x^2 + x^3 - Sqrt[1 - 2 x^2 - 2 x^3 + x^4 - 2 x^5 + x^6])/(2 x^3), {x, 0, 50}], x] (* Wesley Ivan Hurt, Dec 02 2021 *)

Crossrefs

Cf. A329691, A329693.

Sequence in context: A093335 A093333 A116085 * A216198 A369708 A085570

Adjacent sequences: A329689 A329690 A329691 * A329693 A329694 A329695

Keyword

nonn,walk

Author

Valerie Roitner, Dec 06 2019

Status

approved