A292437 a(n) is the number of lattice walks from (0,0) to (3*n,3*n) that use steps in directions {(3,0), (2,1), (1,2), (0,3)} and stay weakly below the line y=x.

1, 2, 13, 120, 1288, 15046, 185658, 2380720, 31411376, 423660504, 5814905977, 80956085304, 1140478875656, 16227516683124, 232870988052180, 3366482778363616, 48981220255732960, 716707681487535144, 10539913681632290532, 155697664218428455520, 2309297999296926348448

Offset: 0

Author

Steven Klee, Dec 08 2017

Keywords

• nonn
• walk

Examples

			For n=2, the a(2)=13 paths terminating at (6,6) are
(3, 0), (3, 0), (0, 3), (0, 3)
(3, 0), (2, 1), (1, 2), (0, 3)
(3, 0), (2, 1), (0, 3), (1, 2)
(3, 0), (1, 2), (2, 1), (0, 3)
(3, 0), (1, 2), (1, 2), (1, 2)
(3, 0), (0, 3), (3, 0), (0, 3)
(3, 0), (0, 3), (2, 1), (1, 2)
(2, 1), (3, 0), (1, 2), (0, 3)
(2, 1), (3, 0), (0, 3), (1, 2)
(2, 1), (2, 1), (2, 1), (0, 3)
(2, 1), (2, 1), (1, 2), (1, 2)
(2, 1), (1, 2), (3, 0), (0, 3)
(2, 1), (1, 2), (2, 1), (1, 2)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..834
• Jackson Evoniuk, Steven Klee, Van Magnan, Enumerating Minimal Length Lattice Paths, 2017, also Enumerating Minimal Length Lattice Paths, J. Int. Seq., Vol. 21 (2018), Article 18.3.6.

Crossrefs

Cf. A000108, A007318.

Programs

Maple

b:= proc(l) option remember; `if`(l=[0$2], 1, add(
      (f-> `if`(min(f)<0 or f[1] b([3*n$2]):
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 09 2017

Mathematica

b[l_] := b[l] = If[l == {0, 0}, 1, Sum[Function[f, If[Min[f] < 0 || f[[1]] < f[[2]], 0, b[f]]][l - g], {g, {{3, 0}, {2, 1}, {1, 2}, {0, 3}}}]];
a[n_] := b[{3n, 3n}];
a /@ Range[0, 25] (* Jean-François Alcover, May 13 2020, after Alois P. Heinz *)

Sage

S = [[3,0],[2,1],[1,2],[0,3]]
q = 10
numPathsMat = matrix(q+1,q+1,0)
for m in [0..q]:
    for n in [0..m]:
        count = 0
        for s in S:
            if n-s[1]>=0 and m-s[0]>=n-s[1]:
                count += numPathsMat[m-s[0],n-s[1]]
        numPathsMat[m,n] = count
        numPathsMat[0,0] = 1
print(numPathsMat.diagonal())