login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A292436 Array T read by antidiagonals: T(m,n) is the number of lattice walks of minimal length from (0,0) to (m,n) using steps in directions from {(1,0), (0,1), (2,1), (1,2)}. 0
1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 4, 2, 1, 1, 3, 9, 9, 3, 1, 1, 4, 1, 2, 1, 4, 1, 1, 5, 3, 9, 9, 3, 5, 1, 1, 6, 6, 24, 36, 24, 6, 6, 1, 1, 7, 10, 1, 3, 3, 1, 10, 7, 1, 1, 8, 15, 4, 16, 24, 16, 4, 15, 8, 1, 1, 9, 21, 10, 50, 100, 100, 50, 10, 21, 9, 1, 1, 10, 28, 20, 1, 4, 6, 4, 1, 20, 28, 10, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

LINKS

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

J. Evoniuk, S. Klee, and V. Magnan, Enumerating Minimal Length Lattice Paths, submitted, 2017.

FORMULA

T(m,n) = binomial(m-n,n) for m>=2*n;

T(m,n) = binomial(q+r,r)*binomial(q+r,m-q) for 1/2*n<=m<=2*n, where m+n = 3*q+r with 0<=r<=2;

T(m,n) = binomial(n-m,m) for m<=1/2*n.

EXAMPLE

Array T(m,n) begins

n\m 0    1    2    3    4    5    6    7    8    9   10

0   1    1    1    1    1    1    1    1    1    1    1

1   1    2    1    2    3    4    5    6    7    8    9

2   1    1    4    9    1    3    6   10   15   21   28

3   1    2    9    2    9   24    1    4   10   20   35

4   1    3    1    9   36    3   16   50    1    5   15

5   1    4    3   24    3   24  100    4   25   90    1

6   1    5    6    1   16  100    6   50  225    5   36

7   1    6   10    4   50    4   50  300   10   90  441

8   1    7   15   10    1   25  225   10  120  735   15

9   1    8   21   20    5   90    5   90  735   20  245

10  1    9   28   35   15    1   36  441   15  245 1960

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)

........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: A175466 A214403 A261527 * A184097 A205399 A135303

Adjacent sequences:  A292433 A292434 A292435 * A292437 A292439 A292440

KEYWORD

nonn,walk,tabl

AUTHOR

Steven Klee, Dec 08 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 25 16:14 EST 2018. Contains 299653 sequences. (Running on oeis4.)