A333498 Sum of the heights of all Motzkin paths of length n.

0, 0, 1, 3, 9, 25, 70, 196, 552, 1560, 4423, 12573, 35826, 102310, 292786, 839554, 2411945, 6941593, 20011328, 57779038, 167069317, 483739961, 1402413161, 4070537585, 11827842021, 34403798725, 100167396088, 291903951462, 851380987390, 2485175809878

Offset: 0

Author

Alois P. Heinz, Mar 24 2020

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Wikipedia, Motzkin number

Crossrefs

Cf. A001006, A057585, A097862, A136439, A333504, A333608.

Programs

Maple

b:= proc(x, y, h) option remember; `if`(x=0, h, add(
      b(x-1, y+j, max(h, y)), j=-min(1, y)..min(1, x-y-1)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..35);

Mathematica

b[x_, y_, h_] := b[x, y, h] = If[x == 0, h, Sum[b[x - 1, y + j, Max[h, y]], {j, -Min[1, y], Min[1, x - y - 1]}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 35] (* Jean-François Alcover, May 10 2020, after Maple *)

Formula

a(n) = Sum_{k=1..floor(n/2)} k * A097862(n,k).