A292435 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)}.

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

Offset: 0

Author

Steven Klee, Dec 08 2017

Keywords

• nonn
• tabl
• walk

Examples

			Array T(m,n) begins
n\m    0     1     2     3     4     5     6     7     8     9    10
--------------------------------------------------------------------
[0]    1     1     1     1     2     3     1     3     6     1     4
[1]    1     2     1     4     9     2     9    24     3    16    50
[2]    1     1     4    12     3    15    48     6    36   130    10
[3]    1     4    12     4    21    72    10    64   250    20   150
[4]    2     9     3    21    84    12    88   380    31   255  1215
[5]    3     2    15    72    12    96   460    40   355  1830   101
[6]    1     9    48    10    88   460    44   420  2325   135  1416
[7]    3    24     6    64   380    40   420  2520   155  1740 11046
[8]    6     3    36   250    31   355  2325   155  1860 12600   546
[9]    1    16   130    20   255  1830   135  1740 12600   580  7882
[10]   4    50    10   150  1215   101  1416 11046   546  7882 63056
		

Links

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

Crossrefs

Cf. A007318.

Programs

Sage

S = [[1,0], [0,1], [3,0], [2,1], [1,2], [0,3]]
q = 8 # q = range for m,n; change q for more data
numPathsMat = matrix(q+1,q+1,0)
distMatrix  = matrix(q+1,q+1,0)
for m in [0..q]:
    for n in [0..q]:
        # first determine S-distance to (m,n)
        d = minNeighborDist = max(distMatrix.list()) + 1
        for s in S:
            if m-s[0]>=0 and n-s[1]>=0:
                d = distMatrix[m-s[0],n-s[1]]
            if d < minNeighborDist:
                minNeighborDist=d
        distMatrix[m,n] = minNeighborDist+1
        # next count number of minimal S-paths
        count = 0
        for s in S:
            if m-s[0]>=0 and n-s[1]>=0:
                if distMatrix[m-s[0],n-s[1]]==distMatrix[m,n]-1:
                    count += numPathsMat[m-s[0],n-s[1]]
        numPathsMat[m,n] = count
        numPathsMat[0,0] = 1
print(numPathsMat)

Formula

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