login
A088457
Number of single nodes (exactly one node on that level) for all Motzkin paths of length n.
5
1, 0, 1, 2, 4, 8, 18, 44, 113, 296, 782, 2076, 5538, 14856, 40100, 108936, 297793, 818832, 2263481, 6286498, 17532707, 49077268, 137821247, 388150322, 1095980561, 3101840232, 8797579789, 25001305410, 71179961918, 203000438544, 579876376729, 1658948939262
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
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
Column k=1 of A364386 and of A372014.
Sequence in context: A339837 A100132 A176720 * A006786 A125809 A245176
KEYWORD
nonn
AUTHOR
Michael Somos, Oct 01 2003
EXTENSIONS
a(30)-a(31) from Alois P. Heinz, Jul 21 2023
STATUS
approved