login
Total number of nodes summed over 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)}.
5

%I #16 Oct 24 2021 04:41:03

%S 1,2,6,16,45,126,357,1024,2979,8800,26422,80688,250705,792568,2548620,

%T 8331568,27667109,93241152,318569656,1102246040,3857916552,

%U 13644697000,48716177272,175417870080,636493447625,2325399611652,8548381939932,31599848465276

%N Total number of nodes summed over 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)}.

%H Alois P. Heinz, <a href="/A333106/b333106.txt">Table of n, a(n) for n = 0..1668</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>

%F a(n) ~ c * 4^n / sqrt(n), where c = 0.0019335749177095597674777855613451543338378695415042866523284... - _Vaclav Kotesovec_, Oct 24 2021

%p b:= proc(x, y) option remember; `if`(x=0, 1, add(

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

%p end:

%p a:= n-> (n+1)*b(n, 0):

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

%t b[x_, y_] := b[x, y] = If[x == 0, 1,

%t Sum[b[x-1, y+j], {j, -Min[1, y], Min[Max[1, y], x-y-1]}]];

%t a[n_] := (n+1) b[n, 0];

%t a /@ Range[0, 29] (* _Jean-François Alcover_, Apr 05 2021, after _Alois P. Heinz_ *)

%Y Cf. A333070, A333105, A333107, A333608.

%K nonn

%O 0,2

%A _Alois P. Heinz_, Mar 07 2020