A329689 - OEIS

A329689

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

1, 1, 0, 1, 2, 1, 1, 4, 5, 3, 7, 16, 16, 16, 40, 66, 65, 99, 211, 288, 329, 603, 1079, 1372, 1897, 3529, 5538, 7219, 11431, 20076, 29305, 41141, 68970, 113103, 162229, 245454, 411984, 642006, 939016, 1491348, 2444027, 3715023, 5619485, 9095842, 14510185, 22008169, 34300205, 55456432, 86830187, 133182523, 211375518, 338423557, 525898418, 818766393, 1308164859, 2073414046, 3226270813, 5084761609, 8117959191, 12786484606

(list; graph; refs; listen; history; text; internal format)

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

LINKS

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

FORMULA

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

D-finite with recurrence: +(n+4)*a(n) -a(n-1) +a(n-2) -2*n*a(n-3) +(-4*n+11)*a(n-4) +a(n-5) +(n-6)*a(n-6)=0. - R. J. Mathar, Jan 09 2020

EXAMPLE

a(7)=4 since we have the following 4 excursions of length 7: UHUHDDH, UHUHDHD, UHDHUHD and HUHUHDD.

CROSSREFS

Cf. 329690.

Sequence in context: A134172 A208061 A078047 * A270952 A143392 A090668

Adjacent sequences: A329686 A329687 A329688 * A329690 A329691 A329692

KEYWORD

nonn,walk

AUTHOR

Valerie Roitner, Dec 06 2019

STATUS

approved