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

Links

Table of n, a(n) for n=0..90.

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.

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

Example

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

Prog

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

Crossrefs

Cf. A007318.

Sequence in context: A046214 A232088 A115413 * A319094 A069283 A319430

Adjacent sequences: A292432 A292433 A292434 * A292436 A292437 A292438

Keyword

nonn,tabl,walk

Author

Steven Klee, Dec 08 2017

Status

approved