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

Comments

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

Links

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

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

Example

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

Prog

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

Crossrefs

Cf. A018838, A120399.

Sequence in context: A236306 A153239 A229502 * A141661 A278521 A195910

Adjacent sequences: A356356 A356357 A356358 * A356360 A356361 A356362

Keyword

nonn,tabl,walk,easy

Author

Johan Westin, Nov 10 2022

Status

approved