cp's OEIS Frontend

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.

%I A292437 #34 May 13 2020 19:01:57
%S A292437 1,2,13,120,1288,15046,185658,2380720,31411376,423660504,5814905977,
%T A292437 80956085304,1140478875656,16227516683124,232870988052180,
%U A292437 3366482778363616,48981220255732960,716707681487535144,10539913681632290532,155697664218428455520,2309297999296926348448
%N 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.
%H A292437 Alois P. Heinz, <a href="/A292437/b292437.txt">Table of n, a(n) for n = 0..834</a>
%H A292437 Jackson Evoniuk, Steven Klee, Van Magnan, <a href="http://fac-staff.seattleu.edu/klees/web/minpaths.pdf">Enumerating Minimal Length Lattice Paths</a>, 2017, also <a href="https://www.emis.de/journals/JIS/VOL21/Klee/klee2.html">Enumerating Minimal Length Lattice Paths</a>, J. Int. Seq., Vol. 21 (2018), Article 18.3.6.
%e A292437 For n=2, the a(2)=13 paths terminating at (6,6) are
%e A292437 (3, 0), (3, 0), (0, 3), (0, 3)
%e A292437 (3, 0), (2, 1), (1, 2), (0, 3)
%e A292437 (3, 0), (2, 1), (0, 3), (1, 2)
%e A292437 (3, 0), (1, 2), (2, 1), (0, 3)
%e A292437 (3, 0), (1, 2), (1, 2), (1, 2)
%e A292437 (3, 0), (0, 3), (3, 0), (0, 3)
%e A292437 (3, 0), (0, 3), (2, 1), (1, 2)
%e A292437 (2, 1), (3, 0), (1, 2), (0, 3)
%e A292437 (2, 1), (3, 0), (0, 3), (1, 2)
%e A292437 (2, 1), (2, 1), (2, 1), (0, 3)
%e A292437 (2, 1), (2, 1), (1, 2), (1, 2)
%e A292437 (2, 1), (1, 2), (3, 0), (0, 3)
%e A292437 (2, 1), (1, 2), (2, 1), (1, 2)
%p A292437 b:= proc(l) option remember; `if`(l=[0$2], 1, add(
%p A292437       (f-> `if`(min(f)<0 or f[1]<f[2], 0, b(f)))(l-g),
%p A292437        g=[[3, 0], [2, 1], [1, 2], [0, 3]]))
%p A292437     end:
%p A292437 a:= n-> b([3*n$2]):
%p A292437 seq(a(n), n=0..25);  # _Alois P. Heinz_, Dec 09 2017
%t A292437 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}}}]];
%t A292437 a[n_] := b[{3n, 3n}];
%t A292437 a /@ Range[0, 25] (* _Jean-François Alcover_, May 13 2020, after _Alois P. Heinz_ *)
%o A292437 (Sage)
%o A292437 S = [[3,0],[2,1],[1,2],[0,3]]
%o A292437 q = 10
%o A292437 numPathsMat = matrix(q+1,q+1,0)
%o A292437 for m in [0..q]:
%o A292437     for n in [0..m]:
%o A292437         count = 0
%o A292437         for s in S:
%o A292437             if n-s[1]>=0 and m-s[0]>=n-s[1]:
%o A292437                 count += numPathsMat[m-s[0],n-s[1]]
%o A292437         numPathsMat[m,n] = count
%o A292437         numPathsMat[0,0] = 1
%o A292437 print(numPathsMat.diagonal())
%Y A292437 Cf. A000108, A007318.
%K A292437 nonn,walk
%O A292437 0,2
%A A292437 _Steven Klee_, Dec 08 2017