A333647 Number of nonnegative lattice paths from (0,0) to (n,0) such that slopes of adjacent steps differ by at most one, assuming zero slope before and after the paths.

1, 1, 1, 2, 4, 8, 16, 34, 74, 169, 397, 953, 2319, 5732, 14370, 36466, 93468, 241767, 630499, 1656372, 4380128, 11652459, 31168689, 83788315, 226272531, 613632359, 1670604607, 4564607998, 12513715526, 34412992018, 94912212872, 262484672621, 727770127583

Offset

0,4

Comments

The maximal height in all paths of length n is floor(ceil(n/2)^2/4) = A008642(n-3) for n>2.

Links

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

Alois P. Heinz, Animation of a(9) = 169 paths

Wikipedia, Counting lattice paths

Maple

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

Mathematica

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

Crossrefs

Cf. A008642, A225338, A333678, A333679, A333680, A333682.

Sequence in context: A096812 A006981 A003427 * A045648 A248890 A308245

Adjacent sequences: A333644 A333645 A333646 * A333648 A333649 A333650

Keyword

nonn

Author

Alois P. Heinz, Mar 31 2020

Status

approved