A292435 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

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