A333679 Sum of the heights of all 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.

0, 0, 0, 1, 3, 8, 20, 53, 137, 375, 1035, 2878, 7988, 22308, 62642, 176692, 499818, 1418228, 4035568, 11512449, 32916181, 94313011, 270757747, 778694171, 2243200705, 6471953522, 18699169766, 54098598824, 156706773404, 454457344755, 1319382151919, 3834346819731

Offset

0,5

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..100

Alois P. Heinz, Animation of A333647(9) = 169 paths with height sum a(9) = 375

Wikipedia, Counting lattice paths

Maple

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

Mathematica

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

Crossrefs

Cf. A008642, A333647, A333678, A333680.

Sequence in context: A295346 A027220 A305823 * A230953 A026995 A018035

Adjacent sequences: A333676 A333677 A333678 * A333680 A333681 A333682

Keyword

nonn

Author

Alois P. Heinz, Apr 01 2020

Status

approved