login
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.
4

%I #16 Apr 26 2021 05:22:53

%S 0,0,0,1,3,8,20,53,137,375,1035,2878,7988,22308,62642,176692,499818,

%T 1418228,4035568,11512449,32916181,94313011,270757747,778694171,

%U 2243200705,6471953522,18699169766,54098598824,156706773404,454457344755,1319382151919,3834346819731

%N 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.

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

%H Alois P. Heinz, <a href="/A333679/b333679.txt">Table of n, a(n) for n = 0..100</a>

%H Alois P. Heinz, <a href="/A333647/a333647.gif">Animation of A333647(9) = 169 paths with height sum a(9) = 375</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>

%p b:= proc(x, y, t, h) option remember;

%p `if`(x=0, h, add(b(x-1, y+j, j, max(h, y)),

%p j=max(t-1, -y)..min(x*(x-1)/2-y, t+1)))

%p end:

%p a:= n-> b(n, 0$3):

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

%t b[x_, y_, t_, h_] := b[x, y, t, h] =

%t If[x == 0, h, Sum[b[x - 1, y + j, j, Max[h, y]],

%t {j, Max[t - 1, -y], Min[x(x - 1)/2 - y, t + 1]}]];

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

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

%Y Cf. A008642, A333647, A333678, A333680.

%K nonn

%O 0,5

%A _Alois P. Heinz_, Apr 01 2020