login
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

%I #34 May 13 2020 19:01:57

%S 1,2,13,120,1288,15046,185658,2380720,31411376,423660504,5814905977,

%T 80956085304,1140478875656,16227516683124,232870988052180,

%U 3366482778363616,48981220255732960,716707681487535144,10539913681632290532,155697664218428455520,2309297999296926348448

%N 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 Alois P. Heinz, <a href="/A292437/b292437.txt">Table of n, a(n) for n = 0..834</a>

%H 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 For n=2, the a(2)=13 paths terminating at (6,6) are

%e (3, 0), (3, 0), (0, 3), (0, 3)

%e (3, 0), (2, 1), (1, 2), (0, 3)

%e (3, 0), (2, 1), (0, 3), (1, 2)

%e (3, 0), (1, 2), (2, 1), (0, 3)

%e (3, 0), (1, 2), (1, 2), (1, 2)

%e (3, 0), (0, 3), (3, 0), (0, 3)

%e (3, 0), (0, 3), (2, 1), (1, 2)

%e (2, 1), (3, 0), (1, 2), (0, 3)

%e (2, 1), (3, 0), (0, 3), (1, 2)

%e (2, 1), (2, 1), (2, 1), (0, 3)

%e (2, 1), (2, 1), (1, 2), (1, 2)

%e (2, 1), (1, 2), (3, 0), (0, 3)

%e (2, 1), (1, 2), (2, 1), (1, 2)

%p b:= proc(l) option remember; `if`(l=[0$2], 1, add(

%p (f-> `if`(min(f)<0 or f[1]<f[2], 0, b(f)))(l-g),

%p g=[[3, 0], [2, 1], [1, 2], [0, 3]]))

%p end:

%p a:= n-> b([3*n$2]):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Dec 09 2017

%t 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 a[n_] := b[{3n, 3n}];

%t a /@ Range[0, 25] (* _Jean-François Alcover_, May 13 2020, after _Alois P. Heinz_ *)

%o (Sage)

%o S = [[3,0],[2,1],[1,2],[0,3]]

%o q = 10

%o numPathsMat = matrix(q+1,q+1,0)

%o for m in [0..q]:

%o for n in [0..m]:

%o count = 0

%o for s in S:

%o if n-s[1]>=0 and m-s[0]>=n-s[1]:

%o count += numPathsMat[m-s[0],n-s[1]]

%o numPathsMat[m,n] = count

%o numPathsMat[0,0] = 1

%o print(numPathsMat.diagonal())

%Y Cf. A000108, A007318.

%K nonn,walk

%O 0,2

%A _Steven Klee_, Dec 08 2017