login
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
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
Sequence in context: A236306 A153239 A229502 * A141661 A278521 A195910
KEYWORD
nonn,tabl,walk,easy
AUTHOR
Johan Westin, Nov 10 2022
STATUS
approved