|
%I #22 Mar 15 2020 12:05:32
%S 1,1,1,1,2,1,1,1,1,1,2,4,4,4,2,3,9,12,12,9,3,1,2,3,4,3,2,1,3,9,15,21,
%T 21,15,9,3,6,24,48,72,84,72,48,24,6,1,3,6,10,12,12,10,6,3,1,4,16,36,
%U 64,88,96,88,64,36,16,4,10,50,130,250,380,460,460,380,250,130,50,10,1,4,10,20,31,40,44,40,31,20,10,4,1
%N Array T read by antidiagonals: T(m,n) = number of lattice walks of minimal length from (0,0) to (m,n) using steps in directions from {(1,0), (0,1), (3,0), (2,1), (1,2), (0,3)}.
%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.
%F G.f.: Sum(T(m,n)*x^m*y^n,m>=0,n>=0) = Sum(binomial(q+r,r)*(x^3+x^2*y+x*y^2+y^3)^q*(x+y)^r,q>=0,0<=r<=2).
%e Array T(m,n) begins
%e n\m 0 1 2 3 4 5 6 7 8 9 10
%e --------------------------------------------------------------------
%e [0] 1 1 1 1 2 3 1 3 6 1 4
%e [1] 1 2 1 4 9 2 9 24 3 16 50
%e [2] 1 1 4 12 3 15 48 6 36 130 10
%e [3] 1 4 12 4 21 72 10 64 250 20 150
%e [4] 2 9 3 21 84 12 88 380 31 255 1215
%e [5] 3 2 15 72 12 96 460 40 355 1830 101
%e [6] 1 9 48 10 88 460 44 420 2325 135 1416
%e [7] 3 24 6 64 380 40 420 2520 155 1740 11046
%e [8] 6 3 36 250 31 355 2325 155 1860 12600 546
%e [9] 1 16 130 20 255 1830 135 1740 12600 580 7882
%e [10] 4 50 10 150 1215 101 1416 11046 546 7882 63056
%o (Sage)
%o S = [[1,0], [0,1], [3,0], [2,1], [1,2], [0,3]]
%o q = 8 # q = range for m,n; change q for more data
%o numPathsMat = matrix(q+1,q+1,0)
%o distMatrix = matrix(q+1,q+1,0)
%o for m in [0..q]:
%o for n in [0..q]:
%o # first determine S-distance to (m,n)
%o d = minNeighborDist = max(distMatrix.list()) + 1
%o for s in S:
%o if m-s[0]>=0 and n-s[1]>=0:
%o d = distMatrix[m-s[0],n-s[1]]
%o if d < minNeighborDist:
%o minNeighborDist=d
%o distMatrix[m,n] = minNeighborDist+1
%o # next count number of minimal S-paths
%o count = 0
%o for s in S:
%o if m-s[0]>=0 and n-s[1]>=0:
%o if distMatrix[m-s[0],n-s[1]]==distMatrix[m,n]-1:
%o count += numPathsMat[m-s[0],n-s[1]]
%o numPathsMat[m,n] = count
%o numPathsMat[0,0] = 1
%o print(numPathsMat)
%Y Cf. A007318.
%K nonn,tabl,walk
%O 0,5
%A _Steven Klee_, Dec 08 2017
|
