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

1, 1, 1, 3, 3, 2, 5, 9, 8, 10, 23, 32, 32, 56, 106, 131, 164, 310, 499, 617, 932, 1682, 2451, 3269, 5426, 9067, 12757, 18650, 31507, 49381, 70446, 110111, 182073, 275332, 407683, 657438, 1053990, 1581022, 2430364, 3935375, 6159050, 9334508, 14715327, 23606027, 36518354, 56308374

Offset

0,4

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

Formula

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

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

Example

a(4)=3 because we have 3 such excursions of length 4, namely UHDH, HUHD and HUDH.

Crossrefs

Cf. 329689.

Sequence in context: A359484 A186111 A186813 * A293521 A285443 A110898

Adjacent sequences: A329687 A329688 A329689 * A329691 A329692 A329693

Keyword

nonn,walk

Author

Valerie Roitner, Dec 06 2019

Status

approved