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

Author

Michael Somos, Oct 01 2003

Keywords

• nonn

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).

Examples

			[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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..750

Crossrefs

Cf. A001006, A051485, A152880.

Column k=1 of A364386 and of A372014.

Programs

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 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 *)

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))}

Extensions

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