|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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):
|
|
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];
|
|
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,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|