login
A329672
Number of meanders of length n with Motzkin-steps avoiding the consecutive steps UU.
2
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.
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
KEYWORD
nonn,walk
AUTHOR
Valerie Roitner, Nov 26 2019
STATUS
approved