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

Example

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)

Maple

b:= proc(l) option remember; `if`(l=[0$2], 1, add(
      (f-> `if`(min(f)<0 or f[1]<f[2], 0, b(f)))(l-g),
       g=[[3, 0], [2, 1], [1, 2], [0, 3]]))
    end:
a:= n-> 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 *)

Prog

(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())

Crossrefs

Cf. A000108, A007318.

Sequence in context: A209217 A000180 A215715 * A317196 A192460 A004122

Adjacent sequences: A292434 A292435 A292436 * A292438 A292439 A292440

Keyword

nonn,walk

Author

Steven Klee, Dec 08 2017

Status

approved