A329672 Number of meanders of length n with Motzkin-steps avoiding the consecutive steps UU.

1, 2, 4, 9, 20, 46, 107, 252, 599, 1435, 3460, 8389, 20437, 49996, 122758, 302401, 747114, 1850696, 4595370, 11435380, 28513149, 71225270, 178219696, 446637759, 1120946389, 2817089354, 7088656546, 17858286741, 45039810918, 113711798916, 287369435649, 726905294670, 1840328917065

Offset

0,2

Comments

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

Links

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

Formula

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

D-finite with recurrence (n+2)*a(n) +(-3*n-5)*a(n-1) +(-3*n+2)*a(n-2) +(5*n+2)*a(n-3) +(11*n-19)*a(n-4) +(9*n-32)*a(n-5) +2*a(n-6) +2*(-n+6)*a(n-7)=0. - R. J. Mathar, Jan 25 2023

Example

a(2)=4 since we have 4 meanders of length 2 avoiding UU, namely UH, UD, HU and HH.

Crossrefs

Cf. A004148 (shifted by 1) which counts excursions avoiding consecutive UU steps. See also A329673 and A329674 which count meanders avoiding consecutive HH and DD respectively.

Sequence in context: A317097 A252354 A052806 * A218552 A110198 A104508

Adjacent sequences: A329669 A329670 A329671 * A329673 A329674 A329675

Keyword

nonn,walk

Author

Valerie Roitner, Nov 26 2019

Status

approved