A333608 - OEIS

%I #16 May 12 2020 08:41:06

%S 0,0,1,3,9,25,70,200,584,1742,5304,16471,52120,167885,549856,1828897,

%T 6170108,21087458,72923515,254880303,899454849,3201729220,11486266036,

%U 41497996004,150879471934,551723923040,2027990653855,7489507917594,27777837416779,103427750936183

%N Sum of the heights of all nonnegative lattice paths from (0,0) to (n,0) where the allowed steps at (x,y) are (1,v) with v in {-1,0,...,max(y,1)}.

%C The maximal height in all paths of length n is A103354(n-1).

%H Alois P. Heinz, <a href="/A333608/b333608.txt">Table of n, a(n) for n = 0..500</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Motzkin_number">Motzkin number</a>

%p b:= proc(x, y, h) option remember;

%p      `if`(x=0, h, add(b(x-1, y+j, max(y, h)),

%p       j=-min(1, y)..min(max(1, y), x-y-1)))

%p     end:

%p a:= n-> b(n, 0$2):

%p seq(a(n), n=0..29);

%t b[x_, y_, h_] := b[x, y, h] = If[x == 0, h, Sum[b[x - 1, y + j, Max[y, h]], {j, -Min[1, y], Min[Max[1, y], x - y - 1]}]];

%t a[n_] := b[n, 0, 0];

%t a /@ Range[0, 29] (* _Jean-François Alcover_, May 12 2020, after Maple *)

%Y Cf. A103354, A333105, A333106, A333107, A333498, A333504.

%K nonn

%O 0,4

%A _Alois P. Heinz_, Mar 28 2020