OFFSET
0,4
COMMENTS
a(n) is the number of Motzkin excursions with an odd number of humps.
A Motzkin excursion is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), never goes below the x-axis, and terminates at the altitude 0.
A hump is an occurrence of the pattern UHH...HD (the number of 0's in the pattern is not fixed, and can be 0).
LINKS
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger. Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Algorithmica (2019).
FORMULA
G.f.: (-2*t^2 - sqrt((1-t^2)*(1-4*t+3*t^2)) + sqrt((1+t^2)*(1-4*t+5*t^2))) / (4*t^2*(1-t)).
D-finite with recurrence +n*(n+2)*(5*n^2-105*n+454)*a(n) +(5*n^4+365*n^3-2348*n^2-614*n+1530)*a(n-1) +(-195*n^4+950*n^3+2838*n^2-8804*n+1530)*a(n-2) +(605*n^4-5865*n^3+13255*n^2+2724*n-14400)*a(n-3) +(-605*n^4+7370*n^3-27409*n^2+29410*n+4140)*a(n-4) +(-5*n^4-65*n^3+1418*n^2-7270*n+12690)*a(n-5) +(195*n^4-1850*n^3+492*n^2+31376*n-58950)*a(n-6) -5*(n-6)*(121*n^3-1227*n^2+2411*n+3042)*a(n-7) +75*(n-6)*(n-7)*(8*n^2-37*n-12)*a(n-8)=0. - R. J. Mathar, Mar 06 2022
EXAMPLE
For n = 4 the a(4) = 7 paths are UDHH, HUDH, HHUD, UHDH, HUHD, UHHD, UUDD.
MAPLE
b:= proc(x, y, t, c) option remember; `if`(y>x or y<0, 0, `if`(x=0, c,
b(x-1, y-1, 0, irem(c+t, 2))+b(x-1, y, t, c)+b(x-1, y+1, 1, c)))
end:
a:= n-> b(n, 0$3):
seq(a(n), n=0..35); # Alois P. Heinz, Apr 15 2019
MATHEMATICA
b[x_, y_, t_, c_] := b[x, y, t, c] = If[y > x || y < 0, 0, If[x == 0, c, b[x-1, y-1, 0, Mod[c+t, 2]] + b[x-1, y, t, c] + b[x-1, y+1, 1, c]]];
a[n_] := b[n, 0, 0, 0];
a /@ Range[0, 35] (* Jean-François Alcover, May 11 2020, after Maple *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrei Asinowski, Apr 15 2019
STATUS
approved