OFFSET
0,4
COMMENTS
A Motzkin path of length n is a sequence [y(0),...,y(n)] such that |y(i)-y(i+1)| <= 1, 0=y(0)=y(n)<=y(i).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..750
EXAMPLE
[0,0,0,1,0], [0,0,1,0,0], [0,1,0,0,0], [0,1,2,1,0] are the a(4) = 4 sequences.
MAPLE
b:= proc(x, y, h, c) option remember; `if`(y<0 or y>x, 0,
`if`(x=0, c, add(b(x-1, y-i, max(h, y),
`if`(h=y, 0, `if`(h<y, 1, c))), i=-1..1)))
end:
a:= n-> b(n, 0$2, 1):
seq(a(n), n=0..31); # Alois P. Heinz, Jul 25 2023
MATHEMATICA
b[x_, y_, h_, c_] := b[x, y, h, c] = If[y<0 || y>x, 0, If[x == 0, c, Sum[b[x-1, y-i, Max[h, y], If[h == y, 0, If[h < y, 1, c]]], {i, -1, 1}]]];
a[n_] := b[n, 0, 0, 1];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Oct 23 2023, after Alois P. Heinz *)
PROG
(PARI) {a(n)=local(p0, p1, p2); if(n<0, 0, p1=1; polcoeff(sum(i=0, n, if(p2=(1-x)*p1-x^2*p0, p0=p1; p1=p2; (x^i/p0)^2), x*O(x^n)), n))}
CROSSREFS
KEYWORD
nonn
AUTHOR
Michael Somos, Oct 01 2003
EXTENSIONS
a(30)-a(31) from Alois P. Heinz, Jul 21 2023
STATUS
approved