A088457 Number of single nodes (exactly one node on that level) for all Motzkin paths of length n.

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

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

Cf. A001006, A051485, A152880.

Column k=1 of A364386 and of A372014.

Sequence in context: A339837 A100132 A176720 * A006786 A125809 A245176

Adjacent sequences: A088454 A088455 A088456 * A088458 A088459 A088460

Keyword

nonn

Author

Michael Somos, Oct 01 2003

Extensions

a(30)-a(31) from Alois P. Heinz, Jul 21 2023

Status

approved