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