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

1, 2, 6, 16, 45, 126, 357, 1024, 2979, 8800, 26422, 80688, 250705, 792568, 2548620, 8331568, 27667109, 93241152, 318569656, 1102246040, 3857916552, 13644697000, 48716177272, 175417870080, 636493447625, 2325399611652, 8548381939932, 31599848465276

Offset

0,2

Links

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

Wikipedia, Counting lattice paths

Wikipedia, Motzkin number

Formula

a(n) ~ c * 4^n / sqrt(n), where c = 0.0019335749177095597674777855613451543338378695415042866523284... - Vaclav Kotesovec, Oct 24 2021

Maple

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

Mathematica

b[x_, y_] := b[x, y] = If[x == 0, 1,
     Sum[b[x-1, y+j], {j, -Min[1, y], Min[Max[1, y], x-y-1]}]];
a[n_] := (n+1) b[n, 0];
a /@ Range[0, 29] (* Jean-François Alcover, Apr 05 2021, after Alois P. Heinz *)

Crossrefs

Cf. A333070, A333105, A333107, A333608.

Sequence in context: A126285 A026163 A005717 * A025266 A074403 A378341

Adjacent sequences: A333103 A333104 A333105 * A333107 A333108 A333109

Keyword

nonn

Author

Alois P. Heinz, Mar 07 2020

Status

approved