A356359 Square array T(m,n) read by antidiagonals: T(m,n) = number of ways a knight can reach (0, 0) from (m, n) on an infinite chessboard while always decreasing its Manhattan distance from the origin, for nonnegative m, n.

1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 2, 2, 0, 2, 2, 4, 2, 4, 4, 2, 4, 4, 6, 9, 6, 9, 6, 4, 12, 17, 14, 17, 17, 14, 17, 12, 34, 35, 35, 40, 36, 40, 35, 35, 34, 70, 74, 84, 86, 90, 90, 86, 84, 74, 70, 148, 170, 185, 195, 205, 206, 205, 195, 185, 170, 148

Offset: 0

Author

Johan Westin, Nov 10 2022

Keywords

• nonn
• tabl
• walk
• easy

Comments

The sequence has eight-fold symmetry, since T(m,n) = T(n,m) and T(m,n) = T(|m|, |n|).

Examples

			There are no knight's moves from (0, 1) which decrease the Manhattan distance, so T(0, 1) = 0.
From (1, 3) you can reach the origin by (-1, 2) -> (0, 0) or (2, 1) -> (0, 0), hence T(1, 3) = 2.
From (2, 3) the possible routes are:
  (0, 4) -> (-1, 2) -> (0, 0)
  (0, 4) -> (1, 2) -> (0, 0)
  (3, 1) -> (1, 2) -> (0, 0)
  (3, 1) -> (2, -1) -> (0, 0)
Hence T(2, 3) = 4.
Array begins:
      m=0    1    2     3     4      5      6      7       8       9      10
     +---------------------------------------------------------------------------
  n=0|  1,   0,   0,    0,    2,     4,     4,    12,     34,     70,    148, ...
    1|  0,   0,   1,    2,    2,     6,    17,    35,     74,    170,    389, ...
    2|  0,   1,   0,    4,    9,    14,    35,    84,    185,    412,    929, ...
    3|  0,   2,   4,    6,   17,    40,    86,   195,    445,   1013,   2284, ...
    4|  2,   2,   9,   17,   36,    90,   205,   466,   1058,   2406,   5491, ...
    5|  4,   6,  14,   40,   90,   206,   476,  1097,   2525,   5761,  13140, ...
    6|  4,  17,  35,   86,  205,   476,  1112,  2566,   5914,  13648,  31273, ...
    7| 12,  35,  84,  195,  466,  1097,  2566,  6002,  13884,  32115,  74129, ...
    8| 34,  74, 185,  445, 1058,  2525,  5914, 13884,  32428,  75304, 174436, ...
    9| 70, 170, 412, 1013, 2406,  5761, 13648, 32115,  75304, 176026, 409435, ...
   10|148, 389, 929, 2284, 5491, 13140, 31273, 74129, 174436, 409435, 957106, ...
		

Links

• Johan Westin, Table of n, a(n) for n = 0..20099 (the first 200 antidiagonals).

Crossrefs

Cf. A018838, A120399.

Programs

Python

from functools import cache # requires Python 3.9
KNIGHT_MOVES = ((1, 2), (2, 1), (-1, 2), (-2, 1),
                (1, -2), (2, -1), (-1, -2), (-2, -1))
def manhattan(x, y):
    return abs(x) + abs(y)
@cache
def A356359(m, n):
    if (m, n) == (0, 0):
        return 1
    value = 0
    for move in KNIGHT_MOVES:
        new_m, new_n = m + move[0], n + move[1]
        if manhattan(new_m, new_n) < manhattan(m, n):
            value += A356359(new_m, new_n)
    return value

Formula

T(m, n) = T(m-2, n+1) + T(m-2, n-1) + T(m-1, n-2) + T(m+1, n-2) for m, n >= 2.

T(1, n) = T(-1, n-1) + T(0, n-2) + T(2, n-2).

T(0, n) = 2*T(1, n-2).