Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #60 Dec 18 2022 21:51:21
%S 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,
%T 17,14,17,12,34,35,35,40,36,40,35,35,34,70,74,84,86,90,90,86,84,74,70,
%U 148,170,185,195,205,206,205,195,185,170,148
%N 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.
%C The sequence has eight-fold symmetry, since T(m,n) = T(n,m) and T(m,n) = T(|m|, |n|).
%H Johan Westin, <a href="/A356359/b356359.txt">Table of n, a(n) for n = 0..20099</a> (the first 200 antidiagonals).
%F 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.
%F T(1, n) = T(-1, n-1) + T(0, n-2) + T(2, n-2).
%F T(0, n) = 2*T(1, n-2).
%e There are no knight's moves from (0, 1) which decrease the Manhattan distance, so T(0, 1) = 0.
%e From (1, 3) you can reach the origin by (-1, 2) -> (0, 0) or (2, 1) -> (0, 0), hence T(1, 3) = 2.
%e From (2, 3) the possible routes are:
%e (0, 4) -> (-1, 2) -> (0, 0)
%e (0, 4) -> (1, 2) -> (0, 0)
%e (3, 1) -> (1, 2) -> (0, 0)
%e (3, 1) -> (2, -1) -> (0, 0)
%e Hence T(2, 3) = 4.
%e Array begins:
%e m=0 1 2 3 4 5 6 7 8 9 10
%e +---------------------------------------------------------------------------
%e n=0| 1, 0, 0, 0, 2, 4, 4, 12, 34, 70, 148, ...
%e 1| 0, 0, 1, 2, 2, 6, 17, 35, 74, 170, 389, ...
%e 2| 0, 1, 0, 4, 9, 14, 35, 84, 185, 412, 929, ...
%e 3| 0, 2, 4, 6, 17, 40, 86, 195, 445, 1013, 2284, ...
%e 4| 2, 2, 9, 17, 36, 90, 205, 466, 1058, 2406, 5491, ...
%e 5| 4, 6, 14, 40, 90, 206, 476, 1097, 2525, 5761, 13140, ...
%e 6| 4, 17, 35, 86, 205, 476, 1112, 2566, 5914, 13648, 31273, ...
%e 7| 12, 35, 84, 195, 466, 1097, 2566, 6002, 13884, 32115, 74129, ...
%e 8| 34, 74, 185, 445, 1058, 2525, 5914, 13884, 32428, 75304, 174436, ...
%e 9| 70, 170, 412, 1013, 2406, 5761, 13648, 32115, 75304, 176026, 409435, ...
%e 10|148, 389, 929, 2284, 5491, 13140, 31273, 74129, 174436, 409435, 957106, ...
%o (Python 3)
%o from functools import cache # requires Python 3.9
%o KNIGHT_MOVES = ((1, 2), (2, 1), (-1, 2), (-2, 1),
%o (1, -2), (2, -1), (-1, -2), (-2, -1))
%o def manhattan(x, y):
%o return abs(x) + abs(y)
%o @cache
%o def A356359(m, n):
%o if (m, n) == (0, 0):
%o return 1
%o value = 0
%o for move in KNIGHT_MOVES:
%o new_m, new_n = m + move[0], n + move[1]
%o if manhattan(new_m, new_n) < manhattan(m, n):
%o value += A356359(new_m, new_n)
%o return value
%Y Cf. A018838, A120399.
%K nonn,tabl,walk,easy
%O 0,11
%A _Johan Westin_, Nov 10 2022