login
Number of 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)}.
7

%I #23 Oct 24 2021 04:33:08

%S 1,1,2,4,9,21,51,128,331,880,2402,6724,19285,56612,169908,520723,

%T 1627477,5180064,16766824,55112302,183710312,620213500,2118094664,

%U 7309077920,25459737905,89438446602,316606738516,1128566016617,4048230694964,14604517154115

%N Number of 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="/A333105/b333105.txt">Table of n, a(n) for n = 0..1673</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) >= A001006(n) with equality only for n <= 6.

%F a(n) ~ c * 4^n / n^(3/2), 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-> b(n, 0):

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

%t b[x_, y_] := b[x, y] = If[x == 0, 1, Sum[b[x - 1, y + j],

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

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

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

%Y Cf. A001006, A230556, A333069, A333106, A333107, A333608.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Mar 07 2020